CT56102

The Fastest Route of Amberfield

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the wheat plains of Amberfield close for winter, Jatin must finish the routes ledger - one figure at a time. 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 <= 1339; 0 <= m <= 4017; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 1294 3411 1 1294 413 847 852251 101 346 757538 33 565 724630 501 570 5610 643 967 387202 788 837 622597 27 668 188557 14 270 772728 592 1285 891200 967 1101 35947 726 1153 806573 409 426 947364 757 990 170521 751 943 93532 1227 1255 477605 224 604 672947 758 886 598681 95 1027 101276 680 822 3626 20 583 501865 1066 1104 924814 31 1033 128444 84 173 227810 753 1103 420113 667 1070 628064 32 41 945612 286 851 787958 868 1117 44117 378 679 965702 671 724 309436 692 797 866766 508 598 985907 157 593 647512 18 1286 565701 832 848 131412 236 407 821444 638 779 987598 542 714 586238 690 705 302407 778 1059 476865 996 1218 193788 58 123 70476 32 490 637946 266 1044 348366 482 1064 557853 351 688 213077 557 835 79953 899 1022 830946 321 686 181411 460 731 210770 585 1140 685428 11 845 954522 910 10…
Output: 1260362

Example 2:

Input: 663 2150 1 663 56 569 824411 365 515 876941 539 576 36457 116 589 496117 460 511 64823 161 345 852700 326 603 866900 107 477 636179 405 600 733858 74 481 774181 482 632 524091 540 580 670461 111 154 296126 34 583 283522 294 559 556858 340 348 725048 359 409 317662 153 591 348713 131 258 375605 12 90 359017 168 346 493954 296 605 475879 411 533 10548 93 638 784013 592 610 879991 105 539 306389 27 61 393379 254 377 477309 175 297 923125 276 307 892456 119 627 824709 20 241 763886 385 398 839374 231 274 506619 174 252 833871 34 121 334924 338 531 238237 1 183 366258 411 549 62081 364 576 490368 397 542 113274 19 627 201728 336 644 512080 49 642 498411 11 504 523075 46 122 145720 429 495 157624 257 344 191155 159 310 951035 143 174 431755 383 564 63842 267 463 814348 277 502 956685 282 604 522…
Output: 1242000

Example 3:

Input: 858 1514 1 858 405 548 923550 175 391 184588 361 762 837977 124 793 547596 416 455 508456 91 447 702640 414 651 769795 250 699 971692 374 802 749599 465 567 109943 152 733 357719 617 785 101939 528 775 609177 16 118 274294 396 806 352471 434 796 536729 15 347 544686 166 272 640979 34 161 846099 306 757 627390 136 145 655740 245 679 722138 125 583 304102 492 789 556090 51 218 272069 750 792 178908 15 693 362884 14 606 351132 512 821 38385 325 511 999596 641 762 323592 653 697 5589 752 773 685324 10 181 197411 388 479 253276 569 654 150987 477 512 407689 36 809 271313 393 595 329905 225 605 98775 426 850 15887 497 798 279334 238 726 928844 556 666 941272 39 558 493138 181 470 716473 320 410 220212 64 782 677264 69 124 655112 443 594 714080 571 855 279029 236 637 308946 20 365 852555 115 182 …
Output: 2000719

Constraints:

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

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