CT58223

The Slitherwick Fastest Route

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

At the eel marshes of Slitherwick, Rosa records each canals 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 <= 1191; 0 <= m <= 3573; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 327 3233 1 327 7 21 517596 120 198 676776 80 181 821496 67 80 862356 273 315 368735 73 282 650738 13 325 249375 182 186 763473 143 269 147614 157 179 68591 124 279 10280 141 320 538187 102 311 571722 124 138 842969 157 180 870200 249 285 962662 140 188 721174 234 265 624379 208 246 504168 221 305 414962 176 289 268109 31 300 742212 36 150 317966 7 33 723974 193 274 729190 53 144 289882 148 260 801598 151 164 432286 3 108 575378 62 85 14550 80 278 472830 55 215 189972 207 240 366530 36 222 72643 71 313 386975 199 250 871568 83 153 362288 6 135 929686 33 36 302888 67 228 339615 232 303 571437 36 213 578403 10 266 698155 176 184 69704 156 310 834076 61 100 468330 230 262 366646 85 201 512181 47 265 428920 148 289 780834 29 104 932786 150 323 593134 12 30 940652 174 297 778397 51 108 773112 21…
Output: 270343

Example 2:

Input: 857 856 1 857 446 505 554906 37 265 275602 141 257 551805 64 215 161372 683 737 196197 593 789 446274 444 497 778292 445 614 988794 544 644 399289 271 581 358019 426 795 26535 121 346 219760 109 561 4140 112 229 212241 100 795 701352 397 806 136542 398 759 154378 473 842 151356 349 651 661932 125 203 690753 464 634 223486 171 206 857760 68 708 639265 102 263 11631 461 670 441030 43 764 368853 242 784 459220 362 410 771989 241 637 138718 209 460 254081 166 622 50674 685 687 56303 484 485 613684 88 808 419876 80 754 553860 234 619 224622 216 665 778943 56 498 482770 687 811 118973 451 766 505542 32 729 377114 259 511 136906 278 599 65869 329 465 230084 149 319 535232 315 418 44529 117 187 642806 487 633 428429 201 600 986701 417 747 453048 91 472 943241 359 716 401037 799 816 855722 494 623 …
Output: 3125950

Example 3:

Input: 270 1948 1 270 118 121 641408 90 231 145205 83 254 83445 252 258 326114 24 96 785420 119 143 943675 51 127 503949 18 120 219626 31 178 474993 103 145 280371 105 268 749613 80 229 9913 115 142 497997 17 246 528988 133 170 812105 47 68 490066 8 225 377297 77 107 707110 70 102 179837 152 257 947709 3 109 924032 20 71 483442 20 217 133891 19 43 517730 205 251 928508 143 150 627217 95 145 949762 131 158 988761 139 172 516421 29 185 758712 170 265 825831 120 258 383987 75 256 25044 158 198 967990 151 240 146308 67 139 113055 22 74 194786 39 267 783497 59 177 122733 58 143 243236 153 256 401990 6 65 481169 59 137 392874 145 239 12943 45 186 703910 194 219 976904 86 110 299301 44 120 601384 7 136 415696 71 77 567601 181 207 834841 69 191 279263 137 145 121212 1 247 893000 31 264 791466 73 171 1748…
Output: 414098

Constraints:

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

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