CT63328

Lakshya's Ledger of routes

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

In the beacon hill of Lantern Tor, Lakshya the tallyman keeps careful count of the routes. Schedule the next expedition, 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 <= 1130; 0 <= m <= 3390; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 18 153 1 18 11 18 914 7 8 795 1 9 171 12 18 791 7 9 887 1 8 199 9 16 674 1 18 257 14 18 787 12 15 496 1 17 883 7 17 949 17 18 727 6 15 285 3 11 597 6 18 964 4 8 449 6 9 681 1 7 526 2 8 812 6 13 506 3 10 373 16 18 877 10 15 401 5 15 37 4 5 585 2 12 535 2 16 988 11 16 191 8 12 834 9 13 145 9 10 307 10 11 692 1 3 478 7 14 276 4 18 261 14 15 112 1 6 373 13 17 98 9 14 687 5 10 829 3 7 835 3 15 456 13 15 775 10 14 535 11 13 80 11 14 361 8 18 908 3 18 159 5 16 68 13 18 462 6 10 317 4 11 701 10 12 955 7 10 322 7 12 178 7 11 661 13 16 893 8 10 110 2 18 204 1 15 241 2 9 506 3 4 787 12 16 540 4 15 377 2 7 798 4 7 275 10 16 366 10 13 827 2 4 431 1 12 890 7 15 897 8 15 302 9 17 856 4 10 965 1 2 758 11 15 93 6 14 644 3 5 848 11 17 537 14 17 428 11 12 778 6 7 337 5 18 679 9 15 977 3 9 835 1 13 531 9 12 9…
Output: 257

Example 2:

Input: 18 153 1 18 9 14 621 2 8 596 6 14 283 3 15 515 4 16 555 3 11 194 9 15 596 5 10 942 4 15 368 6 13 901 4 17 519 8 17 69 2 16 219 10 12 870 17 18 85 11 17 470 2 6 674 2 3 722 5 18 803 8 12 876 1 11 981 5 14 962 1 6 697 3 6 675 7 15 544 11 14 126 5 17 982 4 11 324 14 15 914 5 16 334 1 8 895 7 9 717 9 18 577 16 17 189 7 13 199 2 12 104 4 7 110 1 17 263 3 18 897 11 13 500 13 16 318 2 18 81 2 15 699 4 12 737 7 8 731 4 6 195 4 8 375 8 14 148 3 13 684 6 9 692 2 4 847 7 10 557 5 8 153 7 14 502 8 9 114 5 12 703 1 2 940 11 18 289 4 9 421 1 15 105 4 13 867 6 15 670 1 14 87 14 17 441 3 16 247 3 10 675 8 10 846 8 13 731 7 11 601 3 12 349 8 18 553 1 13 499 2 10 116 6 10 418 12 15 722 2 17 387 6 7 4 2 11 30 12 16 992 6 8 340 6 12 41 12 18 284 15 18 240 4 14 3 6 16 278 15 16 180 3 17 545 1 10 644 7 18 816 1…
Output: 166

Example 3:

Input: 375 2890 1 375 53 287 481 4 196 401 144 228 785 187 218 201 32 212 968 3 44 370 99 255 165 73 213 82 110 205 40 113 356 362 213 264 470 272 293 56 120 302 506 35 74 883 2 12 636 68 361 448 8 96 948 135 324 199 230 297 70 6 85 624 10 274 579 190 309 793 34 358 204 284 319 509 26 176 352 85 330 888 255 322 226 130 327 577 207 248 247 6 29 50 131 230 282 94 182 477 159 235 348 63 367 723 48 50 65 154 336 816 174 290 454 208 245 69 160 375 564 151 205 811 119 147 690 241 349 684 256 297 295 7 46 325 173 210 463 239 321 542 38 322 224 45 176 941 75 109 404 127 235 1000 190 374 574 81 136 368 12 97 906 65 131 919 36 348 313 120 200 780 71 256 633 44 294 552 313 322 91 76 283 493 73 83 172 88 202 104 31 225 625 253 372 682 2 195 117 1 366 671 146 168 656 23 66 199 87 321 318 168 232 208 245 258 7…
Output: 474

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Lakshya's Ledger of routes - MEDIUM Coding Problem | CodeTikki