CT57540

The Cable Plan Beneath Needlepoint

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the pine barrens of Needlepoint opens only for a perfect tally of roads. Harish 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 <= 919; 0 <= m <= 2757; 0 <= w <= 1000000.

Example 1:

Input: 62 1299 32 44 904512 20 58 782085 27 50 632162 18 19 266693 4 15 464489 5 10 261476 18 29 648423 32 43 522439 29 58 792605 50 57 844367 14 36 344174 7 22 781836 5 54 779146 15 56 534727 16 54 719909 13 19 832070 21 30 484965 31 54 243642 12 47 192578 9 49 346792 21 33 862393 12 28 280238 33 49 784898 43 53 465726 42 60 226357 22 57 557011 45 59 766188 18 27 52958 14 57 552576 34 44 520830 2 45 287380 6 20 674140 13 38 526442 28 52 343944 33 38 508240 45 47 345264 38 50 688002 50 51 744190 27 48 521043 52 56 537251 20 28 167498 2 44 249760 1 4 154975 38 56 518254 3 42 605967 26 32 739283 36 42 305406 28 47 162711 9 43 678780 8 45 679599 4 7 379674 2 30 443164 18 53 232887 2 56 507325 4 46 630268 18 57 178505 15 43 737038 18 62 726916 4 40 985039 13 34 883688 4 54 681759 51 56 147304 2 3 775…
Output: 1583691

Example 2:

Input: 115 2669 21 93 127360 37 56 58859 86 89 449089 1 85 201587 44 70 85263 90 98 942738 6 28 359558 71 112 500939 37 73 629171 41 51 484059 30 35 605972 82 89 556132 31 37 395358 13 30 427370 27 68 698742 3 63 837485 15 61 84846 43 112 321858 33 109 89253 53 57 836600 24 107 176271 21 103 902723 19 44 406489 57 111 37750 57 83 848484 18 103 708242 42 67 287168 2 79 473616 26 99 373014 23 32 240614 11 29 942863 9 34 826274 46 112 373112 6 77 766339 6 78 583813 64 103 247745 6 15 82486 99 107 454401 17 92 299424 38 78 591529 8 114 518654 24 75 960637 4 6 557676 25 95 147585 60 61 711484 9 92 519907 92 114 362268 99 102 106838 22 46 41875 35 106 912361 54 115 222468 18 29 305970 3 47 508205 35 96 118778 95 105 585550 15 64 974098 26 62 454095 44 54 868983 69 87 421233 6 75 880909 50 102 888828 10…
Output: 3079949

Example 3:

Input: 174 341 51 166 291606 31 53 779468 62 171 333154 66 131 598130 96 123 872022 164 168 750100 46 96 726797 3 67 108017 125 144 891446 5 51 72538 19 137 742226 91 171 886233 61 91 396046 78 81 884906 15 85 764218 94 141 368553 53 64 536168 15 126 940536 54 172 423663 9 39 741758 61 130 407220 56 121 521866 16 153 455401 30 141 889224 41 52 118444 85 128 598851 26 113 517037 36 147 551906 3 173 270912 30 84 546741 84 121 176231 119 155 672276 51 105 610227 101 123 884004 84 145 555395 151 170 751312 29 123 289766 104 162 160890 2 6 327494 18 95 516357 31 63 604381 59 160 503679 120 137 276407 122 128 448926 100 166 781224 114 134 434094 8 82 921900 24 137 802377 81 118 545208 104 171 669952 54 128 370746 91 139 594348 52 170 199083 50 130 198899 26 122 466214 18 52 471750 44 61 456632 81 139 1…
Output: -1

Constraints:

1 <= n <= 919; 0 <= m <= 2757; 0 <= w <= 1000000.

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