CT53785

Sable's Silver roads

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the orchard lands of Applerun, Sable the scribe keeps careful count of the roads. win the guild's seasonal contest, every figure matters. 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 <= 1272; 0 <= m <= 3816; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 1261 1260 1 1261 515 1026 428935 138 990 149255 271 816 739926 100 263 197139 759 1199 853803 27 995 639283 13 747 281719 230 715 647257 768 971 457922 178 586 99368 697 1163 545816 315 1114 678713 693 779 684665 19 462 242983 620 1052 183608 526 579 906515 324 866 463233 266 517 837328 460 1117 52904 228 880 533372 633 1205 644416 243 817 555749 345 1035 532669 915 975 952248 248 260 938351 739 785 38799 778 1030 221955 165 586 648073 566 574 928012 210 1025 475026 937 1062 563715 869 1182 51681 629 922 749941 483 870 316418 383 1044 559926 441 1077 588574 705 1094 249790 156 900 201453 827 1026 51772 624 785 787828 348 509 350481 723 763 940046 316 853 94211 290 526 382122 286 336 19255 712 1107 5220 268 301 103413 59 1166 663862 172 778 306163 440 457 739358 143 1233 402909 91 687 71853…
Output: 6445047

Example 2:

Input: 271 1343 1 271 193 265 861919 41 65 980763 62 84 190489 80 146 945020 74 214 518052 110 236 981639 162 213 564035 144 210 184917 163 169 707532 74 186 852458 75 183 334731 237 243 466457 109 182 855426 43 103 900024 107 171 236584 96 205 733511 59 146 585881 65 72 392984 191 251 429075 11 257 813447 146 172 242886 96 234 148543 1 205 849841 116 228 1869 131 172 802670 90 201 55239 37 268 213640 87 94 664462 95 233 296448 139 254 518788 58 170 217992 185 228 890310 100 224 878782 127 185 35066 110 154 804142 179 208 337322 149 263 929139 29 124 241687 45 129 276518 145 246 221562 24 196 940703 86 217 457029 36 68 288241 158 271 719697 155 170 164041 6 171 471134 182 205 319412 157 190 249667 128 207 140959 96 254 337536 57 219 614682 30 153 167378 41 238 167735 172 186 570612 76 99 632899 3…
Output: 863607

Example 3:

Input: 520 1932 1 520 87 414 113176 43 434 251581 271 404 517239 271 461 174121 116 392 262563 67 369 372643 170 420 597615 214 241 34171 244 297 825580 119 293 191982 120 296 686947 63 322 180786 484 514 183986 153 355 869819 33 331 469624 79 177 919078 47 154 223242 99 238 932394 294 371 87996 58 156 129522 317 442 515061 98 393 456067 183 325 188653 209 261 956119 66 197 4743 134 454 688793 91 226 834427 29 30 234794 436 439 566446 180 217 502539 320 335 178687 9 261 742858 333 341 336807 286 455 839780 208 429 373331 232 391 749534 276 347 88746 236 405 445682 7 123 207382 300 343 762305 315 418 196695 99 357 926035 261 457 658003 391 428 910511 440 513 438213 291 430 492451 437 475 548633 235 274 186958 65 378 552055 132 388 940708 281 313 429626 249 307 605519 318 499 935217 10 308 938415 2…
Output: 1155428

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Sable's Silver roads - MEDIUM Coding Problem | CodeTikki