CT65234

Wasim and the Cable Plan

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the terraced vines of Grapehollow, Wasim studies rows of routes entries. One clean number will settle the guild's oldest argument. 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 <= 1648; 0 <= m <= 4944; 0 <= w <= 10.

Example 1:

Input: 196 280 120 143 9 135 169 6 10 131 10 99 126 9 111 169 5 53 175 5 59 136 5 5 70 6 25 193 1 110 196 9 24 143 9 130 178 9 126 157 6 182 196 7 53 94 10 43 147 2 13 127 1 37 169 7 52 135 3 46 166 3 14 141 1 16 79 3 26 143 10 22 98 6 120 148 1 117 149 4 102 153 8 82 184 9 46 111 9 84 175 6 81 120 7 56 168 9 7 41 2 55 68 2 79 141 2 25 186 2 119 150 8 109 176 2 6 55 3 50 66 10 72 169 4 26 160 6 98 140 5 44 60 7 161 189 5 25 125 8 10 114 2 1 116 3 3 47 1 63 183 1 113 174 7 52 145 2 9 155 2 43 133 5 34 168 1 37 68 9 37 65 10 40 179 3 83 191 5 57 101 6 129 148 2 116 165 2 134 142 3 63 181 4 24 192 4 15 192 9 80 136 4 1 2 7 6 118 4 146 149 3 24 110 2 15 22 4 137 178 3 15 28 5 6 83 4 69 125 7 16 34 9 48 107 2 26 70 9 152 161 1 14 120 3 78 104 10 39 52 1 32 180 10 146 154 6 58 101 8 52 122 6 26 153 2 1…
Output: -1

Example 2:

Input: 1276 3532 4 1107 2 623 943 6 847 1103 1 526 1208 6 305 1225 8 74 1265 6 380 534 9 332 577 10 783 962 6 442 869 7 1255 1274 7 240 283 3 175 1122 9 166 235 8 705 986 8 796 832 4 530 751 8 150 335 2 128 397 3 638 822 6 977 1048 2 426 944 1 1050 1187 2 1266 1267 2 871 893 9 5 324 10 566 1181 4 307 1217 6 552 1094 3 596 701 6 248 1185 9 459 1236 5 469 1001 2 943 991 8 750 1185 4 361 638 2 274 868 10 412 886 8 763 915 2 178 1067 5 137 715 8 793 830 8 817 1227 6 676 1235 2 43 597 7 834 926 2 13 866 1 723 1236 1 161 1118 5 736 1020 7 455 1099 1 14 464 9 172 1223 7 107 568 6 377 1034 7 334 986 7 5 123 10 839 989 4 1155 1263 3 105 1207 5 190 443 8 511 669 8 588 1097 9 524 1171 5 425 670 5 171 711 8 392 1220 8 631 813 2 367 1166 10 595 834 5 525 526 7 584 1196 9 295 458 7 263 650 10 484 1038 6 305 40…
Output: -1

Example 3:

Input: 1069 2735 119 799 8 806 881 3 745 984 7 528 697 4 879 1000 5 450 506 4 44 537 9 620 945 9 195 960 8 157 614 1 893 1014 2 94 283 4 101 223 8 671 756 5 231 482 1 187 848 5 347 596 2 54 995 2 36 705 9 870 1050 8 26 945 3 184 626 10 598 1030 10 20 534 7 628 942 9 195 210 10 335 968 7 32 1064 10 550 603 6 864 936 5 340 780 1 128 576 1 600 983 2 30 162 5 568 614 9 969 1057 3 790 860 6 106 377 5 306 742 2 605 803 9 662 845 6 251 860 2 75 844 7 134 540 4 10 417 8 118 253 1 309 722 9 496 752 10 212 256 4 600 650 8 120 476 7 11 1028 9 99 710 1 493 515 5 257 619 3 873 895 8 318 927 4 671 852 4 113 260 5 377 922 8 404 1062 2 494 542 6 90 881 2 852 1049 1 132 221 5 527 724 7 502 559 7 389 967 6 22 1064 5 233 260 6 174 916 9 472 1038 7 462 669 3 239 602 6 220 366 4 420 857 10 289 477 5 460 478 1 198 541…
Output: 3016

Constraints:

1 <= n <= 1648; 0 <= m <= 4944; 0 <= w <= 10.

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