CT61091

The Starfall Fastest Route

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the observatory of Starfall; Zaid weighs the day's bridges manifests and starts the calculations. 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 <= 784; 0 <= m <= 2352; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 113 325 1 113 62 100 526107 23 29 740285 18 41 714151 48 81 268125 80 100 694182 74 113 672389 6 10 616308 26 59 135801 43 45 130046 34 90 987078 21 55 71648 9 29 629869 56 75 783760 4 33 47911 96 112 818815 12 16 150534 36 106 635616 11 101 118356 13 56 874709 58 79 591537 68 95 222628 9 83 799819 51 77 845936 42 108 374354 52 65 362327 19 96 432351 13 19 815434 11 26 543927 22 31 818185 33 58 419834 62 89 327282 29 89 824619 29 85 141905 90 98 30745 105 109 658967 24 28 503272 74 97 800075 48 87 113432 13 32 574318 33 43 762961 3 103 347716 57 108 405012 85 106 699789 9 110 578121 60 68 325069 23 55 456553 5 40 338393 11 17 204303 37 66 26536 9 80 51119 62 106 813006 24 73 944255 25 31 568124 33 41 326082 25 68 669508 67 105 539979 5 81 110859 5 90 39372 44 86 877146 1 112 482595 8 80 71…
Output: 1511811

Example 2:

Input: 451 993 1 451 68 307 541423 108 131 817020 242 253 745904 233 362 981541 307 326 156647 12 137 835296 18 402 913320 285 386 351884 97 172 327441 125 267 360733 168 193 265978 223 378 353369 11 169 386854 350 408 948164 255 387 358892 182 313 197899 52 327 684963 93 428 339611 35 342 13422 391 410 666138 9 114 357978 271 417 87553 119 316 999197 101 156 767409 54 247 448836 313 436 103252 101 175 624581 33 297 116362 7 29 412303 178 213 555298 181 278 874563 41 294 310142 16 419 470489 61 154 834790 85 292 865562 115 310 788671 363 427 172957 170 272 223204 26 385 532811 144 384 547435 63 270 231781 3 98 41714 218 231 494169 134 316 836381 327 350 181114 311 353 162902 50 131 607681 13 239 244850 4 250 613493 58 117 959522 102 137 462751 413 427 536420 56 215 828001 134 325 593499 75 78 999…
Output: 1608413

Example 3:

Input: 218 2173 1 218 13 129 102821 41 43 577087 25 174 175695 31 218 107686 101 155 699353 20 164 200820 122 144 48037 64 152 133035 96 141 653592 20 110 737727 46 155 372127 129 186 431817 78 205 359205 17 92 900584 13 86 720328 41 65 958990 129 173 535308 133 209 240475 102 130 453390 170 185 186718 73 130 145510 58 73 528925 88 89 919351 16 87 302032 20 174 844202 58 69 618570 171 183 624793 191 205 987806 44 69 778992 132 146 66025 10 102 416465 161 218 443896 85 194 341844 121 135 281891 159 181 368012 134 155 212477 144 161 125856 55 81 214204 80 128 258029 16 82 984115 143 152 54324 35 95 267980 107 159 81340 53 172 557599 65 70 647576 17 117 946244 34 66 705582 142 186 36454 29 196 888341 37 109 480031 67 91 273293 215 216 854830 21 97 727928 129 198 707216 152 179 226398 113 134 69340 5…
Output: 335102

Constraints:

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

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