CT58232

The Fastest Route of Winterholt

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Vesper found an old ledger of tunnels in the ropewalk attic at the snowberry thicket of Winterholt. The margin notes pose a precise question. Task: An undirected weighted graph is given. Print the shortest-path cost from s to t, or -1 if unreachable. Input format: First line: n m s t. Next m lines: u v w. Output format: Print the shortest distance or -1. Constraints: 1 <= n <= 1302; 0 <= m <= 3906; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 1151 2403 1 1151 94 790 862 831 1139 841 300 362 330 188 786 735 238 411 788 64 459 50 219 372 928 291 502 325 422 656 594 15 882 900 152 160 978 334 837 311 914 1003 12 76 654 453 33 596 726 56 114 319 399 933 463 32 64 646 779 1105 138 398 953 48 525 581 403 879 913 786 8 271 976 4 400 363 616 649 462 95 257 891 736 1148 282 415 712 990 148 1079 75 155 309 662 267 651 901 320 429 523 420 456 476 47 945 634 511 671 380 427 660 956 862 1044 65 709 994 906 282 788 545 552 818 661 224 254 561 251 672 36 725 933 102 515 650 87 756 790 460 136 240 94 47 807 907 397 435 866 440 704 11 45 1080 620 119 584 42 138 747 290 517 586 332 434 693 732 3 542 293 644 820 863 396 760 942 36 289 834 30 548 9 651 999 874 110 231 937 203 945 156 604 1068 230 345 622 808 364 512 437 52 766 54 211 874 394 238 2…
Output: 2950

Example 2:

Input: 1295 1294 1 1295 1103 1165 119 412 1144 540 286 594 376 633 888 190 245 772 498 790 863 869 1033 1126 766 924 1166 714 35 742 321 293 1259 687 941 1013 102 697 1264 73 359 580 579 862 1028 720 1126 1274 452 209 836 648 795 1040 554 107 977 690 312 731 437 343 736 464 484 853 201 159 367 106 218 835 444 679 983 240 984 1288 104 731 970 478 89 333 304 31 567 244 46 603 22 24 424 996 640 715 35 535 951 774 237 909 166 302 814 942 654 879 108 233 1141 38 942 1026 476 88 252 132 348 475 812 233 455 619 541 553 994 553 869 834 233 956 520 211 1241 269 302 567 913 740 1131 410 131 949 35 25 450 648 326 638 871 873 1048 747 229 870 559 675 965 642 23 292 34 250 811 916 288 303 122 1 919 812 252 542 538 885 1103 150 255 1055 187 904 1020 377 30 476 949 543 1160 177 516 600 884 136 729 203 93 249 24…
Output: 5171

Example 3:

Input: 454 1267 1 454 158 164 62 17 104 625 97 211 842 35 377 493 329 434 424 37 51 339 50 207 771 116 162 306 29 402 268 286 387 222 256 392 239 108 205 551 128 386 45 78 431 32 158 258 721 429 451 119 381 387 380 128 410 402 2 419 495 94 220 897 208 355 16 219 352 634 91 414 547 109 299 754 77 196 817 290 304 999 99 410 467 160 321 803 103 126 530 281 429 324 343 410 269 318 396 768 146 285 808 265 424 182 81 120 841 52 309 395 99 231 392 49 132 896 168 190 805 9 97 778 248 388 703 35 387 459 16 286 110 69 239 788 143 316 653 20 420 152 14 27 477 378 380 290 39 165 627 8 66 147 433 435 527 206 415 948 12 359 902 31 370 305 288 315 492 7 388 8 320 372 217 119 161 351 224 388 56 205 236 57 143 373 411 108 287 924 206 351 711 78 311 579 158 376 578 12 365 478 153 262 693 205 439 312 4 39 94 124 25…
Output: 931

Constraints:

1 <= n <= 1302; 0 <= m <= 3906; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

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