CT61696

The Cable Plan at Driftwood

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the quays of Driftwood opens only for a perfect tally of bridges. Milo means to find out. 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 <= 821; 0 <= m <= 2463; 0 <= w <= 1000000.

Example 1:

Input: 608 2374 76 473 826389 120 288 451526 80 500 211856 170 307 181724 156 216 79091 138 540 104538 139 411 498788 260 308 814354 31 92 472109 116 339 441135 373 492 548453 229 260 68845 2 421 799929 115 310 155922 393 545 218989 185 604 151641 27 105 946234 20 26 209019 396 554 177125 78 313 904588 11 503 965664 42 543 821519 34 179 559932 237 253 693876 64 208 922729 176 383 629431 123 159 666268 228 425 448133 53 376 695122 218 553 309065 77 568 537317 223 444 951150 443 543 900762 300 472 952231 131 499 315358 102 312 25247 239 509 228619 71 209 591231 55 408 466784 53 450 981171 6 479 676148 273 410 737705 232 588 881960 40 71 16955 181 450 342523 183 591 979792 211 398 728339 148 174 716617 359 574 11988 13 552 323708 355 474 593649 178 551 105329 595 603 633832 324 598 136030 34 495 635…
Output: 91866013

Example 2:

Input: 745 1707 303 482 325181 330 677 483681 576 579 435744 87 395 169059 645 654 369821 531 691 696490 216 441 300478 168 188 650721 579 588 886143 10 158 713297 62 331 338949 17 167 455976 136 658 452261 229 442 914634 488 503 850545 271 281 273532 313 489 652237 510 650 836140 167 452 751319 7 560 442763 209 739 821401 189 498 929569 208 279 544495 129 442 660166 7 559 569014 198 309 95493 443 609 762505 80 721 242320 181 655 120499 130 343 368207 174 533 563369 242 714 833347 141 407 632047 526 692 903854 225 372 134075 11 588 545249 445 716 543456 211 280 238348 180 703 621912 297 650 350863 467 593 275503 88 122 12771 167 336 766803 49 622 534523 287 620 483796 55 219 817484 439 469 972837 188 644 590669 373 591 11459 334 476 84211 238 583 976712 258 666 756960 473 637 418502 30 642 9932 4…
Output: 191231514

Example 3:

Input: 131 1354 101 109 373913 22 104 568656 66 113 343895 105 114 40864 82 113 773727 107 123 182226 9 70 972551 40 84 240563 120 124 125717 102 122 571459 52 131 8752 17 77 580000 14 64 827392 43 70 189049 37 63 188579 64 118 752076 80 119 352520 87 108 75422 90 114 587240 40 123 545600 1 122 754635 118 125 22873 5 114 947465 2 14 746090 22 123 618520 60 83 699000 14 82 816073 111 116 407575 9 106 593396 62 105 531932 23 122 941383 48 90 866941 61 126 306444 8 124 631144 13 66 465622 10 73 215508 56 104 820475 2 126 854139 80 86 563367 85 101 693133 27 107 979922 25 98 443020 20 70 140866 29 79 608003 26 61 375563 48 79 970726 92 99 419631 25 38 149924 20 51 959102 38 90 402965 11 27 132769 7 105 105574 44 105 155695 46 111 229896 21 121 697199 62 113 976254 19 88 662239 6 112 837768 6 11 21409…
Output: 8296726

Constraints:

1 <= n <= 821; 0 <= m <= 2463; 0 <= w <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.