CT54800

Farhan Counts the routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Farhan inherited the mint at the anvil district of Hammerfall along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 1135; 0 <= m <= 3405; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 294 293 1 294 70 174 725584 169 293 647056 167 217 441487 126 220 123404 143 207 160726 15 22 767906 232 242 512500 21 160 829036 102 231 268778 76 157 804213 133 167 209244 137 189 201726 36 80 559916 136 204 37507 132 146 871111 39 49 73710 83 149 16895 102 142 190438 21 142 637427 66 209 527651 34 188 662131 70 183 586015 122 153 219417 91 184 209509 91 284 907416 103 132 192465 119 219 641640 170 265 789110 18 282 346185 41 95 46375 27 55 528851 37 147 472499 31 260 364286 65 193 306591 137 286 744343 11 258 462385 72 273 602993 24 188 940862 11 86 807079 151 188 908687 1 195 838758 13 132 875040 47 143 30028 155 210 530819 209 230 898556 259 260 357522 79 131 852803 144 194 360009 187 263 370965 20 163 402400 108 278 319800 15 81 500701 102 145 732526 132 244 645337 140 246 148528 14 …
Output: 3026060

Example 2:

Input: 1026 1025 1 1026 277 865 59156 498 797 957270 369 981 48885 103 839 118547 229 806 626535 232 795 906770 22 225 877869 234 866 225331 263 905 625560 240 566 841732 658 991 96889 20 441 981766 87 541 578249 244 601 656845 246 811 416387 129 728 516434 757 804 905167 944 1015 263526 348 915 128053 558 623 873585 820 993 968615 305 320 265364 222 763 977967 313 440 119714 351 712 548222 683 809 979146 139 523 821920 179 556 298046 220 475 307669 410 564 61518 263 291 438802 573 932 601968 519 718 395762 511 680 873060 313 793 964408 803 902 82052 273 620 97918 1 56 150886 419 461 680101 247 828 374028 113 480 847366 542 543 858144 56 109 680218 330 947 992228 687 952 896543 94 703 238919 937 972 81210 72 337 456228 796 946 339474 711 1006 786546 382 925 288914 629 674 168307 75 453 615809 606…
Output: 4030836

Example 3:

Input: 736 912 1 736 447 598 381664 106 308 111568 630 718 417060 167 634 97507 52 228 282905 19 557 907772 503 694 687460 69 246 137100 253 590 668810 95 359 752794 354 486 504768 394 465 972472 107 404 286333 296 427 255725 416 592 819278 286 323 718339 312 598 427916 79 623 28652 561 735 494210 451 495 586585 196 251 374734 400 598 533340 37 597 299233 203 402 337913 135 572 543525 13 243 179970 505 696 863554 108 503 684092 169 458 930350 439 487 691176 663 687 552562 582 661 710141 347 373 591543 204 423 820415 386 427 326178 637 723 759679 158 496 423669 291 669 248752 103 263 828552 362 646 287633 89 130 744836 289 341 589482 65 333 603070 378 569 78148 141 450 198473 509 537 523173 512 585 593767 520 608 350262 182 334 88064 235 570 336193 472 531 819227 479 662 362625 26 593 366413 283 4…
Output: 1564904

Constraints:

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

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