CT59411

The bridges at Skyharbor

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Legend says the vault under the floating docks of Skyharbor opens only for a perfect tally of bridges. Darian 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 <= 1216; 0 <= m <= 3648; 0 <= w <= 1000000.

Example 1:

Input: 41 310 9 35 647235 16 37 758618 23 31 194810 2 18 154290 2 12 651947 4 11 130851 18 35 224306 7 8 743392 8 40 663978 10 26 812016 11 18 57043 19 27 762634 10 29 813176 20 36 232297 1 22 796803 10 30 864707 22 40 675648 9 32 696839 7 27 579457 5 30 396906 20 21 638077 26 27 971029 16 20 798955 4 23 483601 32 38 701832 23 26 480362 18 25 80146 8 41 7023 5 7 4194 14 23 984776 18 24 418356 9 27 632271 13 36 708366 17 29 698716 18 29 483090 5 26 389943 22 35 824597 31 36 632012 4 21 298623 9 22 333901 2 32 642721 37 41 742883 18 33 655627 21 26 21367 6 14 576034 1 4 726715 5 37 287809 33 37 324515 10 18 22286 29 40 147566 19 35 419770 29 38 292277 29 39 564131 7 40 475079 23 36 602061 24 25 776599 28 29 708274 5 25 130382 7 32 282988 26 38 284292 6 15 952321 2 24 29673 10 24 35555 2 27 961722 8…
Output: 2932129

Example 2:

Input: 270 990 238 263 579930 154 171 218531 70 74 637615 153 235 776445 36 87 795563 41 140 210792 8 148 596946 53 208 378316 79 117 607255 182 215 231459 48 78 258709 30 130 472735 104 249 181359 88 105 31344 49 178 412069 91 208 618375 90 192 499168 147 173 66813 88 186 238749 39 53 881664 34 266 563299 15 108 663878 5 141 949649 16 268 974166 182 254 865290 84 176 463354 7 263 739403 62 192 404459 22 103 942286 104 124 635050 59 170 68494 24 222 657604 124 148 995730 192 235 976523 39 93 905365 6 103 301187 184 231 427221 103 259 419193 58 237 451033 101 156 277302 70 209 761689 147 249 41182 223 242 660075 49 65 19494 27 258 321428 20 196 936858 61 181 396002 155 195 849464 11 21 239535 212 218 684447 56 86 152974 48 54 688736 35 147 34909 36 161 356735 6 169 835732 257 270 173929 104 108 39…
Output: 41583714

Example 3:

Input: 982 3098 244 729 735126 153 247 19284 802 947 313957 2 103 270113 390 903 843226 42 459 950306 470 673 748215 4 268 221875 39 849 667215 790 852 313630 520 967 792294 42 497 332848 384 702 178257 95 687 685587 688 818 261424 684 840 617093 445 910 901231 691 901 480894 57 104 849576 196 299 555233 101 187 360399 749 790 940021 475 864 522044 814 911 210848 121 523 88969 14 683 522066 148 817 449764 309 627 785068 98 615 724797 179 723 610004 166 882 824639 29 377 834627 246 537 108776 890 953 727059 73 145 662009 460 945 713867 261 808 705124 522 733 14097 522 624 940416 34 321 767623 87 190 448715 414 533 410381 372 690 396066 138 464 359629 361 728 696973 38 79 18117 457 755 98655 70 132 9428 1 921 446694 401 763 87069 615 969 274459 552 790 139805 387 396 789482 743 817 773033 88 656 86…
Output: 182018521

Constraints:

1 <= n <= 1216; 0 <= m <= 3648; 0 <= w <= 1000000.

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