CT58472

The Rootwater Fastest Route

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the mangrove channels of Rootwater, Brevin records each corridors 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 <= 773; 0 <= m <= 2319; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 160 2074 1 160 34 103 464587 11 127 679434 41 104 664222 8 101 572130 38 70 538818 135 159 217979 5 99 432714 50 113 471702 29 112 888433 79 98 419758 77 143 883795 53 105 103283 17 98 334962 2 102 824963 49 108 678277 118 142 659206 124 128 47066 45 149 403426 87 150 142541 96 109 847343 98 154 459832 39 126 477616 38 113 595814 76 82 151220 18 96 609001 49 70 547992 65 114 18358 9 114 165286 60 155 791991 79 137 849661 17 94 950186 21 89 195302 21 142 85882 99 149 442357 68 155 228827 11 160 19320 88 152 937498 99 131 5621 112 116 255112 47 119 561554 6 81 333569 28 119 745282 13 107 3772 56 83 568867 98 124 483582 28 137 787405 49 80 238233 7 86 366086 27 49 854601 97 123 768391 11 34 960252 132 139 586971 85 142 248368 9 11 984603 12 48 538981 97 138 173779 61 141 981584 41 115 525231 …
Output: 181611

Example 2:

Input: 637 1973 1 637 33 483 30405 394 557 624048 363 487 81861 104 135 609440 15 476 264410 160 508 249394 288 550 213638 114 476 758173 348 543 659041 169 483 17704 152 335 805023 448 516 216105 31 489 420092 387 534 864018 359 544 949567 293 422 275635 48 302 565712 69 82 621783 328 498 137564 274 445 594012 41 381 835181 191 398 643889 404 592 189385 194 398 708084 25 314 698535 83 329 357788 28 72 115994 308 400 796264 9 324 852928 173 217 420884 20 441 4920 28 434 737412 64 631 626589 88 447 534289 274 462 882138 23 388 164795 515 598 596650 153 463 549027 130 307 459666 463 609 330974 318 476 453211 358 592 241807 126 528 35581 104 293 86578 302 563 800620 370 427 175927 136 593 999442 403 489 600549 596 618 417783 248 286 334736 47 585 524979 44 542 330182 32 433 101794 27 536 147652 380 …
Output: 853271

Example 3:

Input: 131 1063 1 131 13 128 654642 40 70 380248 52 81 393829 8 95 850099 62 64 157243 4 120 44003 24 42 707970 45 85 918313 20 48 224334 28 97 161535 2 25 968416 56 121 80347 47 120 913731 27 49 55470 5 122 754648 1 51 690578 37 73 611889 7 106 854377 71 106 234435 67 101 493629 89 122 197245 41 47 785298 10 53 512715 50 59 242880 6 69 631291 90 124 897788 5 121 106990 8 72 18089 68 84 150882 31 53 181581 1 77 283431 26 131 673210 1 29 532060 100 110 457420 14 35 163079 59 102 552812 82 103 221970 90 93 86694 13 29 263438 19 93 988967 57 128 461882 27 30 500972 60 121 144197 51 61 447240 85 90 443223 51 86 554049 73 82 211184 1 111 519970 37 82 106323 7 115 782126 18 115 775050 15 111 394835 8 131 597277 49 56 9834 23 85 303532 23 44 875161 45 53 555416 96 124 324182 70 95 149144 22 103 32283 9 …
Output: 57043

Constraints:

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

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