CT59605

The Ruby Fastest Route

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Morning light hits the ember mines of Cindercrag as Tarun unrolls the day's manifest of bridges. The tally will decide the next shipment. 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 <= 1152; 0 <= m <= 3456; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 877 956 1 877 2 512 83106 253 768 153548 91 157 885314 410 543 399162 396 818 943706 125 810 685891 123 226 156601 490 667 787456 259 845 694106 11 239 155586 228 471 825428 108 179 400695 496 537 242662 310 745 454820 415 486 855578 475 776 370791 30 39 628641 279 721 878745 77 766 261871 228 602 560747 159 408 549002 81 117 75871 376 430 672236 61 754 300883 282 554 999482 48 240 619473 327 792 746318 363 626 848647 285 767 685492 588 755 95736 380 509 937287 77 407 252742 244 417 807357 372 527 735926 442 568 109516 178 235 668569 10 795 797058 223 470 744578 257 376 218177 121 154 844451 349 690 263758 404 803 29433 165 429 248312 214 640 764035 571 751 323544 28 164 121149 377 758 642405 454 740 862145 653 769 23942 358 476 104709 464 820 269531 2 611 338936 263 555 726119 83 197 2880…
Output: 6560080

Example 2:

Input: 651 2958 1 651 357 553 639722 406 565 490707 195 343 382241 343 610 462721 126 136 864110 518 582 857684 521 591 959115 191 515 83051 23 532 454042 63 607 549750 327 342 925527 2 19 522779 297 625 87925 549 587 400093 116 236 94661 181 368 71475 9 217 715101 564 632 801844 442 648 734203 356 644 97601 258 311 182181 36 228 764608 301 391 70414 524 546 3285 250 628 597891 34 56 177219 588 597 768558 153 631 626311 447 645 932206 107 428 807033 205 264 679940 181 325 254040 26 219 50013 7 602 452902 424 504 274594 51 278 72846 217 622 711146 486 633 994072 451 539 722914 313 499 602655 133 586 181903 406 598 348813 102 360 695616 235 379 949807 100 302 598473 1 208 912776 264 642 575458 152 200 829781 191 491 682947 89 377 48404 150 309 14922 64 602 353022 137 461 222105 211 286 635654 192 6…
Output: 947366

Example 3:

Input: 62 1891 1 62 27 39 593564 32 61 964534 41 45 104452 33 45 780949 20 54 692601 31 38 660819 38 55 268798 39 55 982273 14 47 598740 1 47 931308 35 57 416971 22 52 196063 29 41 467479 5 7 301926 38 41 63137 19 27 863040 30 49 45733 34 48 683941 4 44 504188 10 43 415078 7 54 856588 9 14 902584 27 43 889238 41 58 934848 25 56 81672 3 54 263094 43 62 550945 29 48 355803 17 49 626080 10 41 462862 4 62 797439 20 45 765247 19 46 471486 1 8 428044 11 50 388352 6 35 656021 8 43 920291 21 33 771755 20 29 242935 7 33 77389 42 56 480552 1 29 688812 28 30 817644 11 56 205112 10 56 905058 31 55 741918 27 35 226970 7 35 465397 21 34 532863 29 35 967778 55 58 299680 29 39 89686 26 41 357740 7 43 197089 37 48 763242 49 61 444620 39 49 998425 2 5 330003 2 8 326584 29 43 292071 27 38 146671 25 31 318515 11 59 …
Output: 63382

Constraints:

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

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