CT39787

Kabir's Ledger of roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The tallyman Kabir has been asked to chart the migration season. On the desk lies a long table of roads readings. 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 <= 1053; 0 <= m <= 3159; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 81 1374 1 81 20 76 450119656 12 70 59163448 19 22 939700582 29 36 210943027 69 77 203183391 7 69 465625706 5 31 816552286 59 61 657286727 46 52 304661656 75 79 977240250 56 60 196805926 5 8 187800825 4 55 684866040 20 64 650639250 1 17 6773158 40 55 223221057 56 75 309000248 58 81 652706819 24 76 214563714 4 23 909086259 13 71 95998321 19 40 336324801 37 71 364658669 4 20 442209678 8 31 548917627 40 57 400061255 23 60 347535439 5 57 871382527 43 52 464481877 58 68 926617333 35 59 670357333 44 61 754229368 43 75 257608222 10 24 225131401 16 37 221091739 23 69 640488140 60 80 403235813 36 63 96808184 38 39 647514885 19 41 890427375 16 54 286010668 3 53 959078375 7 64 3325103 5 22 573432939 32 34 524494588 33 77 420585926 24 43 883414378 3 48 243543516 46 58 41030744 47 67 689065654 11 66 464…
Output: 185453586

Example 2:

Input: 272 2512 1 272 12 132 809435274 82 200 639298433 29 74 574101457 159 259 804163371 142 269 808893223 27 218 589656341 82 247 147991088 9 236 945489283 112 171 513923117 81 124 900514393 34 82 615235742 57 173 543062056 13 20 220913675 111 176 13598310 111 223 40069647 112 205 920319081 31 123 696817561 91 143 714509624 132 251 431594078 74 247 649960301 193 226 317218676 13 34 578619475 48 127 589149980 124 161 765960937 70 226 59718699 52 261 212479690 88 198 635128274 45 155 621229325 3 57 634868774 53 251 931937148 182 208 855321008 85 95 764793555 26 109 182983845 71 171 411256501 143 176 58454414 78 210 554278341 68 205 266359519 22 196 595029480 54 160 105898598 208 226 486854275 40 183 928821803 34 129 462707948 11 58 911337451 1 129 291748806 160 191 820459495 31 82 854978234 115 2…
Output: 265163432

Example 3:

Input: 941 1727 1 941 113 637 280656146 367 565 970911817 258 487 643321974 618 880 582589872 383 765 447385813 306 505 74472366 277 430 356553423 9 846 116451973 104 886 753843280 104 838 365474058 10 367 525036112 537 854 25963241 249 919 663844323 279 748 103991112 269 883 746632757 541 569 403847201 512 879 462862452 572 702 779192689 306 728 761634692 67 515 446787794 15 587 117624232 22 561 453532697 74 641 25480281 653 735 462313551 408 655 936635599 298 848 800968666 504 757 408393136 360 933 422173311 427 649 789856570 99 212 998477619 429 458 492868022 281 542 162399798 46 839 902067560 562 778 779829749 110 935 761269657 628 743 406215666 398 523 30782680 196 197 981330396 215 573 888036666 357 795 78561595 151 863 546890177 230 744 279968238 341 938 346593641 417 585 344602408 41 167 …
Output: 1055403202

Constraints:

1 <= n <= 1053; 0 <= m <= 3159; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

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