CT63991

The Fastest Route at Grapehollow

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the terraced vines of Grapehollow, Bram records each bridges 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 <= 844; 0 <= m <= 2532; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 233 657 1 233 10 228 864655174 29 226 798948318 69 226 235712666 180 191 712262745 152 195 678512112 45 139 766473425 19 124 74898906 22 148 720698652 13 150 540817716 51 82 486636602 143 190 175797964 58 75 132050815 183 187 658452985 150 162 317182706 170 211 39612681 118 203 234876491 76 98 459393846 22 165 444590792 86 164 596638705 131 158 543170309 40 52 688284675 81 114 351821646 77 200 827852769 145 213 417969982 198 221 436856246 34 58 20054506 43 138 239161007 193 215 859370636 28 192 193460344 46 221 846647388 9 114 591735947 25 205 31233642 58 148 442046416 144 150 897943731 34 164 663084980 4 59 904337565 3 110 643382778 32 201 694547145 12 31 292369228 55 180 145367668 3 67 391592086 54 128 276447138 99 101 145014611 19 138 965699915 148 215 263417572 38 149 551126356 17 34 1…
Output: 876656137

Example 2:

Input: 89 1568 1 89 51 67 150779893 44 73 31662953 54 86 402964729 3 4 924001251 28 30 745022991 25 38 415345246 39 81 198760482 70 77 476770527 8 16 709969424 21 31 796755874 9 29 119064384 24 50 679703137 38 75 109508648 24 25 482599459 21 53 202198565 41 89 975561738 26 33 977122911 39 70 399769648 14 49 770306438 27 74 873757494 35 38 807364077 29 58 944657086 36 37 473559258 25 31 64013355 7 53 214414210 35 77 904155330 38 63 790158619 1 11 449382919 57 69 320279002 34 57 264848792 16 70 233907122 17 83 543787208 19 75 175397544 14 39 676709478 1 78 975010503 7 19 244661211 82 83 485918324 42 74 50965197 16 43 335356899 32 88 163415530 32 34 446100855 39 49 685078113 5 41 352158550 63 65 580813863 18 66 424842963 51 64 796597411 2 15 268966391 17 67 574155644 17 54 876792759 51 61 69928575 1…
Output: 201464321

Example 3:

Input: 557 2016 1 557 426 537 370435438 258 433 60674246 211 368 547425921 329 493 671821518 4 428 871885920 40 495 719547892 130 241 634899255 314 400 474730038 307 331 576588507 8 416 59804631 69 195 20222463 65 385 818543412 283 418 603785600 221 498 717016657 384 398 279419443 62 255 370480704 75 259 71919487 343 453 173422046 190 352 530700019 217 376 834489378 149 353 846836504 185 445 583765931 184 402 692540931 100 470 412904109 183 450 898915731 104 534 128739000 71 287 4370604 209 426 771327332 439 511 120236354 400 477 408262512 120 467 835636101 138 453 555382376 150 384 47496912 217 234 836957429 128 540 259091964 90 361 84201585 233 251 596938633 187 464 596952753 34 127 886484138 172 507 975083636 105 180 185652363 187 507 337123143 69 273 997554667 81 345 525717488 104 333 6041277…
Output: 1131620919

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Fastest Route at Grapehollow - MEDIUM Coding Problem | CodeTikki