CT57324

Lazy corridors Cable Plan

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the port of Emberfall, Draper records each corridors in a worn leather ledger. The guild wants answers, not guesses. 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 <= 844; 0 <= m <= 2532; 0 <= w <= 1000000.

Example 1:

Input: 740 2149 56 517 253122 306 735 565819 299 459 657841 90 691 487248 293 378 927720 272 542 874852 12 72 571934 333 440 98068 288 688 974032 144 173 260187 405 435 180359 266 270 785501 560 660 54393 159 235 814113 132 379 22784 577 586 101007 220 567 741113 123 316 907784 50 330 581095 50 247 165739 242 674 319216 214 466 470695 327 574 803094 569 737 418604 114 142 617055 464 625 953840 62 194 177996 102 489 970495 23 78 890124 534 734 302256 61 721 690291 499 590 982035 151 715 877730 282 733 183820 548 710 678716 391 410 685574 11 366 911000 68 474 760065 234 492 107473 78 535 54519 600 602 843430 22 610 645554 163 226 67301 323 575 866898 541 600 35593 54 552 70092 20 172 57809 393 421 144245 625 653 935101 479 680 837926 368 637 358211 316 343 857778 91 147 774275 361 609 3974 56 603 5…
Output: 153448792

Example 2:

Input: 44 946 23 29 344408 11 18 714901 3 33 674294 1 12 203647 16 36 234256 2 38 112384 22 38 212607 33 34 389467 13 35 835177 35 37 710537 6 13 40140 12 24 252472 16 17 238752 4 17 17632 15 33 235732 12 22 203613 4 44 348119 1 39 573791 11 31 561666 16 25 975716 9 26 30428 2 32 53234 5 6 767130 14 42 816280 25 34 823700 3 30 859509 14 32 481796 9 14 650526 2 41 424170 18 36 434420 17 32 485922 37 39 773886 6 21 728747 13 38 423594 11 42 879675 21 29 469506 16 39 492576 13 19 145125 22 28 819035 6 35 530856 13 32 91649 19 26 864573 19 36 394450 9 44 358157 15 30 283571 25 43 134439 5 36 390259 2 27 349054 37 44 641226 1 32 407172 16 26 921417 3 39 458380 24 29 995711 14 15 399974 11 14 481337 7 22 177568 3 18 601952 15 31 737727 27 36 682778 6 18 281735 2 5 831444 5 28 124420 12 15 978424 7 25 6…
Output: 1336398

Example 3:

Input: 349 1092 28 304 295299 141 274 536125 17 324 341354 150 220 292344 122 140 341940 132 249 454196 84 200 162864 88 239 729141 185 209 226570 58 115 241128 49 196 88021 216 217 737290 242 281 393216 37 149 992560 232 330 857753 84 202 114548 75 188 538269 213 219 459617 55 138 382101 26 65 479483 93 323 551257 108 128 115683 152 204 234133 208 262 307308 1 246 762246 152 343 488359 248 326 142499 26 283 260189 292 323 865417 118 132 140214 115 261 322769 117 313 235081 127 258 488126 1 5 31868 191 224 241045 87 178 611630 38 150 253497 7 311 253630 190 334 900976 48 167 3458 108 200 685412 231 283 563739 2 72 48028 28 246 772420 94 100 655495 60 142 663893 144 334 80224 53 133 188048 188 231 23548 51 174 341111 155 322 777949 30 91 691068 24 101 717439 47 298 440030 58 69 78356 72 111 874496…
Output: -1

Constraints:

1 <= n <= 844; 0 <= m <= 2532; 0 <= w <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Lazy corridors Cable Plan - MEDIUM Coding Problem | CodeTikki