CT61972

The Cable Plan of Rainhaven

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the monsoon port of Rainhaven as Yara unrolls the day's manifest of roads. The tally will decide the next shipment. 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 <= 944; 0 <= m <= 2832; 0 <= w <= 1000000.

Example 1:

Input: 333 1392 95 107 436839 332 333 243912 29 322 754161 57 164 840002 234 311 42962 177 263 37854 51 120 181247 75 298 801882 117 176 63313 54 213 70014 7 80 303511 117 207 759881 247 268 31530 31 109 906982 47 149 373047 162 212 965622 196 223 155906 320 326 294409 292 330 61772 71 307 930198 83 211 17268 63 155 270169 84 94 700649 52 331 762963 30 81 359697 142 180 766111 23 250 871559 102 139 645377 2 318 740901 39 310 725494 50 283 756585 123 161 897730 95 254 211365 103 261 777292 13 290 271418 280 320 298714 188 198 891510 299 321 263855 181 232 661614 31 257 911274 20 292 392540 15 283 49210 60 244 860947 232 297 911969 33 160 668860 142 173 22061 73 184 76221 213 305 44513 41 317 763876 86 107 334064 34 35 959230 156 301 839026 89 94 295618 176 229 682811 30 220 209207 233 245 580439 5…
Output: 48631395

Example 2:

Input: 39 741 3 35 237405 7 8 118450 4 7 440869 20 33 220433 3 14 861326 20 29 398225 6 32 321780 29 35 428052 5 26 468557 17 20 969019 8 31 16377 13 17 260458 2 4 179754 15 39 994891 9 34 219511 2 29 716918 11 35 682111 33 36 920289 4 9 313048 6 34 836609 10 30 914594 18 35 350742 7 14 232846 17 37 496858 21 26 653394 3 37 952156 17 28 938629 21 25 308152 14 29 975297 18 22 362846 10 23 816560 33 38 597704 32 38 504079 27 38 286615 21 38 331829 37 39 728612 5 33 3504 17 19 33071 17 21 657129 14 20 588057 10 24 757072 5 13 898297 4 6 557731 31 32 659282 29 32 326840 2 39 178570 15 24 634755 14 35 77272 26 30 251788 2 11 960250 23 24 344589 23 27 481340 14 23 440991 7 37 311656 21 23 915164 13 30 295105 22 28 79074 8 36 248838 1 16 837241 30 31 584481 15 28 255055 1 3 666542 3 26 459614 19 37 3648…
Output: 1197387

Example 3:

Input: 719 1405 36 370 16071 234 318 219680 155 451 527528 208 396 422353 488 668 547692 620 674 521452 312 408 198012 6 510 517293 165 469 153571 244 649 863915 354 674 104823 67 153 462402 75 125 867788 104 596 348423 57 360 24578 629 641 302871 74 379 294422 148 415 207784 173 485 747334 48 237 301186 78 659 295018 260 525 649476 185 589 76746 25 186 789408 645 659 448747 30 446 37567 143 303 475380 173 578 287944 265 540 292051 54 502 362754 146 356 348216 76 114 38443 151 434 414604 331 524 542998 146 532 905937 95 695 35970 404 484 722300 172 619 415189 104 555 4987 575 593 596827 240 485 846967 107 534 822686 187 272 700784 258 612 441047 189 195 515891 218 718 278037 395 568 334024 26 425 907054 94 486 295919 206 330 289349 43 207 353395 424 474 556055 99 698 203445 55 521 29287 503 610 6…
Output: -1

Constraints:

1 <= n <= 944; 0 <= m <= 2832; 0 <= w <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
The Cable Plan of Rainhaven - MEDIUM Coding Problem | CodeTikki