CT60075

The Cable Plan at Needlepoint

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Every season at the pine barrens of Needlepoint, someone must prepare the guildmaster's brief. This year the task falls to Zaid, armed only with the routes register. 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 <= 1498; 0 <= m <= 4494; 0 <= w <= 10.

Example 1:

Input: 1158 4470 196 770 1 300 961 9 466 680 2 604 968 7 6 932 2 210 331 10 298 560 4 5 419 9 728 743 2 266 610 10 75 771 3 514 1079 6 1 687 6 894 927 6 509 632 6 1064 1112 2 436 473 10 140 674 6 726 1112 10 83 924 2 676 776 1 25 1117 6 768 803 10 994 1096 9 926 1149 5 224 1102 5 631 864 1 462 646 7 815 890 2 954 988 4 390 565 1 736 1071 4 124 805 2 425 501 9 22 393 1 62 877 8 502 511 10 631 942 7 441 456 9 487 793 1 631 1083 1 908 1144 6 961 1005 7 271 647 1 83 736 10 858 975 6 687 1056 3 218 582 2 315 953 1 247 900 5 481 866 8 483 566 5 118 341 4 256 571 7 655 742 10 110 1113 4 399 930 9 355 441 2 697 773 3 716 819 5 48 745 9 755 1141 4 490 569 9 226 449 3 827 1142 1 56 1029 1 113 406 3 815 1066 7 932 1021 4 622 627 8 251 255 9 597 620 1 138 572 10 345 975 5 23 139 8 639 1075 9 627 878 5 111 98…
Output: 2451

Example 2:

Input: 187 1250 20 161 4 23 107 9 135 182 5 52 170 6 75 86 9 5 185 8 11 105 2 61 178 3 52 148 3 43 98 9 73 125 9 49 53 8 18 114 7 14 51 4 61 152 2 147 150 8 160 185 6 5 34 1 26 82 6 46 48 1 38 58 8 138 178 1 87 147 7 37 179 2 161 176 1 19 144 2 83 168 6 25 68 9 32 183 9 105 138 6 169 185 1 106 154 7 140 157 6 9 13 4 30 48 1 114 137 2 45 177 6 82 169 1 10 144 10 129 135 4 24 43 3 4 174 9 15 108 6 62 164 1 125 136 6 33 61 6 101 118 5 2 152 2 6 162 8 3 121 3 61 121 9 12 44 1 116 129 8 35 100 5 28 102 1 51 158 8 62 182 9 3 142 3 105 114 10 94 169 7 38 104 2 30 134 7 17 24 3 132 170 1 73 139 2 44 74 4 23 181 4 102 155 1 78 106 10 132 150 1 96 108 2 21 65 2 103 167 2 2 154 1 95 150 10 10 115 9 23 30 6 25 72 1 54 84 6 63 133 7 76 101 2 33 86 1 1 186 2 81 155 10 25 110 10 61 105 3 35 39 7 162 184 7 131 1…
Output: 259

Example 3:

Input: 783 1502 134 439 5 356 383 6 647 723 2 453 636 5 339 665 4 18 514 10 137 346 5 227 663 9 460 561 4 565 578 5 535 589 8 303 601 5 33 514 10 129 612 1 574 731 6 107 371 6 458 739 8 7 656 9 465 698 1 168 520 5 120 632 4 690 742 1 31 65 7 446 505 5 491 513 3 230 382 2 484 783 9 237 708 10 576 656 1 127 661 10 46 550 10 543 661 3 57 517 7 114 450 6 293 398 1 283 470 8 303 323 9 670 767 6 336 421 9 212 327 2 218 439 9 369 653 7 56 231 3 4 84 9 388 513 2 410 765 6 54 65 7 166 699 2 78 414 5 86 544 1 114 225 7 285 672 7 580 607 7 515 604 6 197 609 6 155 477 7 231 510 8 71 519 1 320 721 2 182 288 8 189 383 10 486 671 1 63 715 5 391 535 10 587 774 4 318 667 1 205 210 7 78 748 10 263 522 4 37 153 9 207 374 6 289 296 6 263 438 9 256 606 10 157 333 5 126 319 8 115 144 4 328 405 6 16 501 9 595 758 10 19…
Output: -1

Constraints:

1 <= n <= 1498; 0 <= m <= 4494; 0 <= w <= 10.

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