CT63372

The Fastest Route of Cascade Vale

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the ribbon falls of Cascade Vale, Nandini records each roads in a worn leather ledger. The guild wants answers, not guesses. 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 <= 1148; 0 <= m <= 3444; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 216 1434 1 216 78 213 679516 162 200 348049 96 152 908847 146 202 953470 100 171 974521 55 97 896625 33 96 143911 24 188 960671 158 183 385822 28 101 297932 37 173 446220 4 208 226986 180 208 817177 6 13 722760 185 189 236650 155 165 515041 19 103 826609 4 127 706130 86 179 986728 190 207 593685 82 161 93447 11 143 998644 70 126 546381 92 119 193910 39 101 783680 166 203 754279 27 79 313894 35 173 439431 38 121 507859 39 199 157241 115 211 689976 138 160 306654 35 125 569570 80 147 685898 131 171 642133 10 157 735932 25 57 851209 173 198 593754 62 113 400838 118 129 685124 94 129 79568 2 115 352826 10 58 906745 28 112 748676 16 198 765031 42 128 756621 64 159 703257 37 45 518271 33 134 517491 43 146 906683 124 177 489809 183 212 918031 14 142 384386 144 214 972536 94 97 96361 62 104 534026…
Output: 150802

Example 2:

Input: 715 2982 1 715 141 667 301682 64 120 660457 369 483 530957 460 603 355438 291 424 821281 395 517 35064 59 558 620430 285 646 434675 102 438 584479 264 359 600994 181 406 859248 223 659 792863 10 617 401774 201 228 71740 7 455 900951 121 390 694713 581 694 700939 220 355 531067 52 538 644001 72 520 752898 191 294 330807 45 464 915545 156 461 606180 196 264 511144 21 493 126015 137 463 1165 43 85 82493 188 563 960655 560 699 884915 97 588 319008 355 462 348361 519 592 587387 434 455 364428 291 358 915792 164 388 727757 54 497 36448 399 678 435938 218 602 813715 126 368 814739 323 552 72030 212 541 980583 108 231 521518 20 341 402732 212 267 980609 275 696 537672 214 618 108476 274 598 900056 393 505 732444 354 378 940832 311 392 804130 239 640 463771 17 106 650921 705 714 355373 230 254 2555…
Output: 987746

Example 3:

Input: 734 831 1 734 101 609 149601 56 388 865684 274 710 500638 397 652 877595 186 425 70501 625 703 634526 363 732 816674 150 315 554939 432 714 970417 309 316 224619 169 200 414611 254 565 53283 128 365 307463 227 649 402666 523 538 78464 36 109 594363 120 515 211476 18 463 575195 209 213 574170 379 533 938660 377 696 430235 356 364 765190 506 668 285959 62 486 225918 98 494 951483 127 456 208574 32 698 876664 122 678 849687 126 206 174903 541 687 731350 65 220 133241 510 668 190085 235 371 668253 186 218 42641 637 688 644252 93 271 852870 105 657 967782 325 684 132539 515 624 503069 18 325 825745 496 614 215343 19 129 964788 82 234 257735 19 183 953542 71 677 940639 182 428 993472 170 174 791848 79 528 307957 70 520 163988 104 147 652256 544 599 439596 178 367 692697 26 427 429449 253 347 741…
Output: 5142352

Constraints:

1 <= n <= 1148; 0 <= m <= 3444; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

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