CT65343

Bram's Fastest Route Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Bram found an old ledger of tunnels in the workshop attic at the fox den of Rustwood. 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 <= 1516; 0 <= m <= 4548; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 1261 1260 1 1261 299 746 269 346 476 989 150 325 113 430 458 373 184 228 971 327 735 636 71 825 678 273 421 373 98 229 153 41 691 470 194 511 208 185 719 834 388 583 233 196 397 296 25 1216 26 28 543 124 673 1032 337 379 719 85 191 686 328 115 911 577 122 239 781 628 842 237 658 907 788 877 995 785 650 979 20 233 628 770 393 1124 190 99 516 144 339 1198 554 930 960 981 514 616 212 321 556 208 298 350 213 1075 1207 853 250 976 708 99 329 982 495 926 982 716 1076 381 827 1019 525 508 1152 163 402 1233 600 253 933 605 406 1256 619 730 1167 676 518 1189 632 820 1052 197 78 185 540 322 1070 431 317 444 516 49 1015 54 966 1087 796 353 371 15 677 757 258 812 864 160 136 375 422 575 1164 294 440 735 394 121 1253 686 907 1161 583 47 470 315 122 483 70 882 1195 997 276 1188 456 303 708 20 150 1140 9…
Output: 4146

Example 2:

Input: 309 3739 1 309 198 270 862 40 163 111 2 53 929 154 306 619 20 247 446 95 178 369 99 157 146 148 297 740 186 278 201 133 248 172 177 199 951 71 74 875 238 287 256 114 304 139 102 112 610 242 288 940 13 175 795 159 163 972 207 233 677 91 128 936 13 35 435 223 229 781 146 232 387 196 306 735 157 176 267 1 131 872 45 293 621 117 194 400 133 226 318 32 267 922 176 269 303 77 305 180 108 309 654 176 181 627 33 216 151 144 247 555 74 214 364 25 63 814 45 113 683 103 121 161 104 226 153 92 198 697 13 145 303 142 269 958 102 308 423 26 163 587 220 258 894 18 199 893 21 217 905 136 285 870 114 214 633 62 151 306 42 63 330 137 228 14 187 241 126 161 306 599 24 271 740 49 226 13 40 257 590 52 53 95 248 307 478 113 282 438 67 184 788 8 242 594 160 202 852 147 216 401 92 309 882 268 295 959 130 284 888 …
Output: 384

Example 3:

Input: 611 4438 1 611 431 473 698 202 516 638 230 589 750 172 312 538 86 609 137 31 173 894 359 524 290 230 378 420 255 299 998 11 147 902 23 46 73 289 302 715 183 399 492 190 410 397 49 483 203 280 348 221 98 297 734 143 541 594 324 357 613 346 556 901 231 511 167 17 419 574 230 405 187 122 288 722 546 606 795 358 503 47 443 610 123 123 408 753 391 516 684 217 336 12 448 487 530 25 77 30 96 206 205 122 301 969 118 585 248 264 390 143 200 579 490 313 318 160 436 445 637 6 362 331 381 477 194 28 75 206 86 423 64 198 347 358 453 595 224 249 580 534 30 197 951 70 124 23 77 455 626 368 585 750 4 538 326 173 569 674 212 376 570 176 353 554 3 528 876 373 389 572 196 262 359 314 575 142 140 248 664 171 224 303 173 197 71 8 488 623 302 361 440 58 601 504 166 421 277 204 338 971 5 193 5 28 92 27 166 432 4…
Output: 344

Constraints:

1 <= n <= 1516; 0 <= m <= 4548; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Loading...
Test Cases:No test cases
No test cases available.