CT58107

Clerk's Ledger of routes

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Clerk inherited the stall at the pine barrens of Needlepoint along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 856; 0 <= m <= 2568; 0 <= w <= 1000000.

Example 1:

Input: 222 1552 10 222 186344 15 169 507368 106 147 947533 129 194 926746 36 40 946993 57 208 796459 162 215 671906 145 158 893572 140 197 615140 96 179 156740 30 37 363357 127 155 129085 19 108 3559 132 214 816625 168 189 495863 14 51 95271 118 141 953942 89 121 386536 118 148 245458 25 110 740672 180 214 966048 52 56 434362 22 50 980472 23 204 917007 165 213 191293 167 169 801781 164 211 901765 11 170 167223 100 175 604208 103 108 227531 61 74 224107 96 198 143322 3 151 144347 107 112 826589 102 217 435201 140 182 390432 47 135 407376 69 91 803825 38 211 612585 3 14 98222 72 198 899308 61 128 498043 126 211 487450 44 104 565851 30 82 759267 82 124 150378 152 167 290067 98 166 38261 30 172 216757 17 185 579147 2 173 478608 23 36 821189 7 31 383184 16 20 411847 52 99 839271 69 171 753000 96 149 4…
Output: 17358428

Example 2:

Input: 811 1661 80 144 72790 284 392 244522 255 580 829038 31 240 669269 588 714 956958 81 572 743460 72 416 583562 571 583 107589 486 755 976517 316 386 947745 390 672 978272 123 226 379142 256 703 198533 492 739 633630 325 725 137447 312 723 577654 349 657 846496 403 654 554860 431 533 398872 22 264 339353 225 551 285097 159 280 63779 481 558 413197 269 381 898074 265 481 55919 399 490 852601 461 608 985922 255 597 676563 429 604 704471 36 485 319624 168 410 302876 396 489 762606 76 171 871161 573 737 257434 436 601 405894 97 325 793394 341 401 135294 148 500 894963 617 682 923670 384 475 256251 148 381 36932 277 775 913958 364 753 942532 61 142 947871 609 704 395101 5 793 703613 218 303 812917 11 584 150450 127 436 407867 430 682 496759 229 569 23992 98 197 290715 494 586 332620 198 461 560411…
Output: -1

Example 3:

Input: 815 2114 113 197 160067 19 121 550206 451 798 665131 377 636 544278 226 525 864766 283 680 891851 424 469 54761 2 586 832290 62 78 76461 501 702 544108 395 774 893379 195 272 156975 225 472 640847 119 288 952896 428 603 747693 350 532 263820 235 695 535252 782 809 798368 379 556 899326 524 559 458694 102 141 581186 331 495 277526 355 647 642407 23 471 681513 658 716 473072 350 808 333318 367 782 48611 583 603 807462 222 516 846606 169 253 27667 409 805 912652 123 680 487424 490 546 894590 159 753 765619 276 482 465135 499 785 929174 233 615 585464 534 780 937439 229 458 632996 183 186 615921 295 553 948373 178 598 601536 156 337 164050 38 528 686640 539 716 883875 352 776 371543 423 514 137843 296 409 255469 691 722 168780 314 607 475298 435 677 265547 401 507 450651 232 242 762903 115 654…
Output: 172361742

Constraints:

1 <= n <= 856; 0 <= m <= 2568; 0 <= w <= 1000000.

Loading...
Test Cases:No test cases
No test cases available.
Clerk's Ledger of routes - MEDIUM Coding Problem | CodeTikki