CT35612

Shepherd and the Fastest Route

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Shepherd found an old ledger of tunnels in the mint attic at the ribbon falls of Cascade Vale. 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 <= 1122; 0 <= m <= 3366; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 413 479 1 413 54 95 958153 74 132 544356 3 93 408293 83 164 100844 100 272 431163 197 360 109315 23 143 768009 297 369 468223 44 185 686838 94 297 674456 81 161 923967 8 131 553516 44 368 267907 16 357 620988 23 406 431074 63 90 754804 148 298 34335 46 183 777563 17 136 861779 39 194 86190 109 308 362045 191 200 668974 206 347 79190 9 202 170001 159 167 976123 94 385 866552 14 60 614121 71 98 485049 249 296 683094 323 385 164002 82 294 962314 306 338 55347 242 274 18679 37 39 40638 182 410 332566 102 294 382820 143 412 631663 324 403 908431 173 235 449696 275 331 455865 105 208 65042 118 390 407362 93 398 130565 194 399 687136 31 285 965693 226 258 483477 307 363 795181 322 329 469575 83 199 641411 327 381 829301 130 389 655741 80 215 801175 18 227 838082 137 358 210053 90 388 698456 23 23…
Output: 3509484

Example 2:

Input: 711 710 1 711 44 658 29995 367 411 254917 224 350 957680 261 492 711099 67 615 879099 424 594 908413 296 626 652528 446 571 213685 517 552 888846 200 697 87506 554 579 345047 137 461 567199 167 683 142732 430 700 638372 272 508 395083 409 648 850809 27 206 317410 174 298 885993 644 671 925261 50 385 669245 291 617 693006 195 357 880797 270 283 639889 81 707 23402 12 588 843480 532 534 378284 307 490 110753 98 347 370176 168 488 886554 27 282 908924 333 616 220057 10 258 544361 75 262 981422 56 655 84006 23 331 987770 189 213 884925 28 587 973475 486 695 701494 116 284 935077 20 134 976654 467 688 164947 172 627 739174 132 397 447230 32 209 599544 150 656 117055 263 408 509395 393 417 260330 182 208 189912 263 539 35296 198 586 771533 36 196 195138 323 455 464046 39 292 281699 24 340 408466…
Output: 3940012

Example 3:

Input: 248 902 1 248 87 234 176804 5 90 151789 96 134 892923 138 208 811835 25 64 249818 115 154 511889 73 235 488646 77 80 23630 118 235 314933 96 181 574438 79 130 461759 26 147 220496 9 134 404047 196 198 860567 33 78 594970 104 232 340301 9 40 717496 17 201 475169 31 86 41139 113 115 70228 93 190 529880 7 39 688008 39 111 572681 51 190 48198 23 175 681796 41 129 116596 88 90 737558 35 129 1293 143 232 75852 9 91 213006 31 116 454210 78 213 773643 3 232 727291 7 160 323300 72 110 139922 136 187 545401 146 189 331715 117 242 117025 117 190 723631 11 112 703414 88 192 468481 66 102 786781 53 230 382469 9 65 860910 104 168 625243 13 84 950962 62 158 828125 228 242 112825 41 169 544326 109 226 73982 7 222 12784 65 168 243403 63 115 384579 148 217 746659 65 231 827544 115 230 217824 34 238 815294 7…
Output: 1309865

Constraints:

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

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