CT60952

The Tuskmore Fastest Route

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Sara inherited the greenhouse at the boar woods of Tuskmore along with its curious bookkeeping system for corridors. Time to make sense of it. 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 <= 1169; 0 <= m <= 3507; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 340 2836 1 340 144 162 144405 107 306 523601 117 258 793073 8 197 78908 38 222 733055 40 333 554331 69 142 552873 36 68 745722 6 282 634984 133 207 662449 43 288 285484 19 64 51305 180 325 523290 129 212 700645 5 296 248082 39 319 680702 145 225 432574 60 305 237007 178 306 736672 61 306 435748 239 316 251733 207 235 52059 18 325 390842 190 251 425301 38 153 561902 158 220 893001 13 70 690575 137 286 223162 5 226 187624 198 218 214208 248 268 949151 223 314 919698 53 307 468726 187 284 482020 152 326 874931 318 320 896861 1 250 252064 31 82 808260 92 327 462101 157 293 923537 163 222 931602 264 330 746548 166 182 189702 107 249 809435 262 335 467602 6 149 13365 127 319 814025 2 96 171558 26 141 650109 70 286 73990 181 285 792037 68 197 606972 130 149 169153 194 240 809421 45 103 906332 232…
Output: 425826

Example 2:

Input: 251 307 1 251 141 216 308731 125 208 345109 7 23 736788 47 56 422686 83 173 256129 130 142 644254 179 250 190727 69 94 920610 142 181 180536 32 67 676772 89 145 395501 9 131 995860 98 235 431326 128 130 898148 168 229 939995 77 222 787552 18 95 932513 86 220 500222 124 136 431721 136 202 17228 152 156 351127 15 109 417257 176 201 236397 12 141 893265 4 250 713455 42 161 867001 14 130 334740 1 142 84574 57 234 607002 39 173 228054 53 146 10744 168 179 41373 201 249 406560 156 233 830362 107 192 583974 89 165 782192 2 250 146120 89 127 829556 86 127 795028 95 207 726332 91 236 479591 31 32 746843 47 78 55397 16 165 896659 202 208 924720 6 246 304071 47 215 185191 8 23 604013 214 221 496455 64 68 596119 18 25 89015 166 213 519317 183 194 352501 39 207 414409 127 141 873742 56 62 156819 223 22…
Output: 1730861

Example 3:

Input: 861 1702 1 861 330 847 737832 357 409 344336 781 817 710862 549 714 252556 562 781 273330 488 751 33648 362 366 220493 402 642 318676 196 638 678240 35 179 578263 6 485 945084 38 565 521997 181 514 605971 68 69 626013 724 851 273765 238 775 773499 533 652 207777 37 47 816135 301 491 308327 409 457 732676 125 540 508370 137 257 730000 127 243 247460 165 737 996018 99 793 81211 194 647 970902 229 643 189397 24 721 171500 560 729 916670 175 212 328771 387 704 133574 75 364 308226 502 708 551996 134 619 414281 301 535 212444 273 638 975121 245 764 790400 386 527 534823 193 333 717358 499 638 370193 307 399 770213 18 269 330396 244 738 587366 105 276 351045 145 373 38580 597 763 201310 577 624 848537 291 377 887279 597 787 1539 44 206 422873 673 842 183833 151 343 828113 206 531 876119 516 653 …
Output: 1865730

Constraints:

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

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