CT57981

The Copper Fastest Route

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Koda found an old ledger of bridges in the loft attic at the shale slopes of Greystone. The margin notes pose a precise question. 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 <= 829; 0 <= m <= 2487; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 470 1273 1 470 308 338 43312710 48 66 859402124 142 285 715729856 253 373 625439208 39 263 440465920 56 188 95181546 219 278 891073988 169 361 670361705 302 305 289575998 84 132 629974696 245 454 901961576 8 394 153060489 310 332 445800904 195 312 209720432 400 432 715296583 134 438 916056848 182 307 737222322 275 466 445698302 298 395 52813498 355 427 135248314 78 331 881141095 35 431 158269356 418 439 538198278 395 424 717748406 38 138 36622465 155 460 183457665 133 330 855173262 87 375 55247676 415 459 489404815 25 115 514838004 129 211 847587281 274 277 865360593 53 136 294021103 59 381 873928659 33 263 808931892 196 433 256626522 8 190 161260491 5 12 34131099 114 426 917304705 141 215 279442725 42 260 47596182 153 407 720528702 251 424 771180261 176 388 213837086 33 211 860375927 72 3…
Output: 2023012091

Example 2:

Input: 153 2245 1 153 33 106 633359878 52 57 623568555 62 122 935943418 142 147 123041553 97 102 652005197 41 63 908389113 22 114 343628715 19 63 974100101 3 110 904128516 9 37 625320896 23 84 643790740 81 117 605491997 144 150 939078412 69 137 582638826 9 18 709218396 67 81 623454558 12 86 939760622 116 120 921633308 55 124 10575119 43 151 959163805 53 91 187744528 47 82 307914199 22 108 502606656 64 89 238088139 126 143 779228452 23 97 81675125 104 144 600972430 85 146 169540848 10 106 566514922 42 111 243612245 60 135 383329461 65 79 559089693 7 79 471164530 58 112 282617163 103 116 46893026 56 129 729684471 59 120 562255641 3 20 845483516 95 119 582267141 21 102 354641480 127 134 170074520 21 63 419020981 89 102 234249722 31 140 223398898 60 140 486827006 67 118 6151725 29 136 930506209 128 1…
Output: 159324779

Example 3:

Input: 118 2233 1 118 52 111 870324682 32 88 391174833 22 42 594341731 7 11 942225380 73 87 678730695 62 104 108736644 85 100 687688822 44 63 838609008 57 82 212422996 50 58 808529515 14 47 184647081 49 71 392863527 12 51 421238552 15 51 234663897 51 68 570230365 42 78 857889143 50 80 213603218 89 118 952684315 81 106 310242469 78 108 913572632 20 118 393385188 50 108 417552889 69 115 376440334 32 44 247388049 27 57 824016070 10 40 956694805 36 102 988978499 12 118 959779749 62 118 14677144 23 105 483532126 9 16 214851315 52 86 668470908 101 106 939815733 53 71 435614393 25 39 417275775 9 92 227051361 28 86 379040180 105 115 515093438 1 38 39746872 17 37 757720898 4 110 334039257 18 88 597237874 95 96 47767691 81 102 620615160 49 65 889697611 44 76 390128555 73 88 515871416 23 91 238345395 16 52 …
Output: 184261390

Constraints:

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

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