CT59974

Ulrica's Ledger of bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Ulrica the valuer watches over the quays of Driftwood's stores of bridges. A careful computation stands between order and chaos. 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 <= 1105; 0 <= m <= 3315; 0 <= w <= 1000.

Example 1:

Input: 68 1686 6 47 1 9 13 171 10 67 355 61 68 291 53 65 337 33 54 198 13 28 398 50 65 47 11 45 201 14 49 999 12 48 619 20 60 356 15 18 685 10 47 96 4 54 504 50 54 35 23 60 448 4 65 270 29 55 106 18 61 652 4 33 228 34 60 833 40 68 845 28 41 586 23 66 953 9 35 331 47 54 291 21 62 377 29 51 835 30 40 104 41 48 717 37 42 287 9 41 764 16 35 737 5 20 737 48 51 824 55 61 574 26 36 98 26 58 670 6 44 80 21 63 556 27 54 330 4 20 494 54 55 643 1 58 945 48 54 704 58 65 409 15 66 938 12 39 331 18 24 812 14 56 907 24 50 546 39 67 61 59 66 578 41 51 97 9 30 196 14 18 599 23 38 235 12 54 962 12 20 532 16 51 670 7 61 287 25 49 250 33 63 709 11 39 35 27 38 604 34 37 145 14 62 770 16 49 945 13 16 195 58 64 240 55 57 667 10 15 163 27 55 685 9 63 751 12 36 257 10 52 183 7 16 292 8 40 533 1 13 384 8 15 462 27 59 890 …
Output: 1712

Example 2:

Input: 285 2905 27 139 662 3 126 204 123 137 281 81 171 763 8 55 940 63 88 3 150 205 170 111 265 245 90 140 773 19 34 430 27 53 975 50 155 839 146 189 467 58 164 842 34 157 851 86 160 785 123 245 273 16 87 948 115 177 327 6 235 176 149 157 591 5 140 27 158 177 499 3 247 604 119 139 659 121 181 926 119 178 250 129 162 121 117 164 185 146 237 338 182 262 317 39 97 316 110 228 547 67 128 256 84 150 822 59 191 975 264 279 609 109 265 892 122 180 778 52 185 347 109 206 827 23 24 379 120 152 828 28 216 906 115 246 598 125 241 451 24 51 782 184 236 396 28 116 868 32 240 167 103 113 750 92 219 350 151 262 816 38 140 639 42 148 191 106 166 710 27 264 322 222 278 318 62 131 643 20 82 312 162 251 454 2 125 236 78 223 499 6 11 32 82 267 78 77 137 538 107 250 834 197 242 370 121 202 215 56 69 751 25 63 397 21…
Output: 15111

Example 3:

Input: 540 2651 144 252 50 191 352 694 378 400 247 58 258 446 81 478 433 371 413 171 246 274 9 182 479 594 139 407 921 46 249 126 331 532 887 190 477 911 278 392 911 225 364 55 296 471 163 92 535 990 106 296 858 93 413 516 86 518 282 101 181 212 90 423 351 275 465 955 288 439 619 82 441 162 33 54 261 334 432 575 61 389 380 93 410 220 385 425 795 234 479 497 58 165 24 23 404 566 39 127 449 31 235 477 165 354 465 57 529 350 426 532 214 100 142 666 66 318 548 47 299 369 294 422 694 287 533 1 278 340 616 471 540 286 268 330 774 46 305 293 48 435 314 87 334 574 288 301 208 196 450 400 348 456 171 216 348 151 366 368 335 102 299 69 182 317 626 31 68 263 222 276 558 212 417 803 196 341 198 19 343 948 144 465 891 348 443 858 264 440 855 259 475 818 257 318 287 29 75 872 440 442 504 378 508 762 98 119 312…
Output: 66752

Constraints:

1 <= n <= 1105; 0 <= m <= 3315; 0 <= w <= 1000.

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