CT59979

Ancient tunnels Cable Plan

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Jarl inherited the observatory at the poppy fields of Scarlet Plain along with its curious bookkeeping system for tunnels. Time to make sense of it. Task: Print the minimum total weight of a spanning tree, or -1 if the graph is not connected. Input format: First line: n and m. Next m lines: u v w. Output format: Print the MST weight or -1. Constraints: 1 <= n <= 996; 0 <= m <= 2988; 0 <= w <= 1000000.

Example 1:

Input: 612 2585 384 486 66752 372 604 698694 79 279 460965 373 475 554248 225 494 586708 402 421 528058 240 553 710064 389 461 384193 111 481 84580 238 462 193893 358 598 947757 441 468 759631 37 327 492534 265 463 957846 167 204 869480 5 363 881372 123 172 352847 315 366 312481 56 438 403280 281 605 581341 173 264 365607 41 169 646684 427 463 200568 53 362 960427 452 536 228455 16 30 675631 144 155 185439 250 524 857520 321 567 644093 291 367 62296 81 323 465617 141 237 903244 99 136 138591 363 364 382334 86 259 780790 144 161 426735 70 183 739578 220 484 520703 493 598 447371 251 560 963021 131 307 867335 48 305 808448 11 226 296610 2 158 80728 288 328 50366 383 538 246400 49 293 956705 410 453 9810 319 488 671252 5 493 156675 48 448 376513 342 449 966381 209 609 13056 228 610 392820 1 355 7274…
Output: 80991456

Example 2:

Input: 51 678 4 31 23902 18 41 27819 9 12 359571 20 21 426409 3 27 519713 1 47 713371 16 23 986503 10 26 869851 31 37 361236 7 25 143426 7 21 69128 9 23 256644 5 21 934171 24 46 177994 6 27 668530 2 48 991829 19 24 793136 25 37 13229 7 10 278250 34 51 946218 9 18 148338 16 43 275607 7 27 484296 23 49 769796 15 18 791716 32 41 653460 20 46 349645 30 35 191322 12 36 794607 37 48 166902 20 31 184976 24 39 420837 1 36 889131 21 45 933863 30 32 918611 7 18 94577 25 46 180920 2 46 546045 31 48 253457 11 20 436908 35 43 83873 11 17 467367 37 45 270787 4 48 523358 27 45 730111 17 31 311352 25 41 131196 9 27 232110 28 47 121964 39 49 933144 14 30 24560 20 48 100530 24 30 795762 27 36 745108 5 11 66450 19 37 662731 31 47 507436 14 37 492868 41 49 12995 12 24 188220 8 12 928719 24 33 141263 22 40 60675 19 2…
Output: 2323566

Example 3:

Input: 491 2069 26 330 938968 183 345 919569 361 417 897599 105 250 944160 197 382 39462 57 127 592170 85 348 784436 28 159 483808 36 144 733545 160 428 9605 88 338 531981 127 203 753076 268 417 839169 387 408 544617 402 412 940120 110 166 244639 11 249 176345 187 313 202806 271 367 577758 81 237 706895 221 269 684693 43 335 168012 287 486 303250 48 247 842459 10 419 112537 74 438 448669 111 209 519786 286 353 215611 125 152 576329 121 366 745678 318 347 677124 137 364 724394 233 403 726237 142 279 355483 130 263 927879 248 445 534158 246 364 853149 53 80 347796 17 26 96320 69 148 636355 84 105 347861 14 234 392557 123 474 589068 136 433 388842 76 311 148107 92 481 609937 37 251 438498 164 452 937658 76 348 239255 112 429 84557 77 88 220626 154 164 61762 242 257 565257 343 395 647522 96 116 68339…
Output: 65579382

Constraints:

1 <= n <= 996; 0 <= m <= 2988; 0 <= w <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Ancient tunnels Cable Plan - MEDIUM Coding Problem | CodeTikki