CT58066

Chavi's Windward corridors

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Deep in the fox den of Rustwood, Chavi studies rows of corridors entries. One clean number will settle the guild's oldest argument. 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 <= 1247; 0 <= m <= 3741; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 172 3128 1 172 48 63 735508 63 92 100361 43 92 97943 149 165 601657 29 48 610919 97 122 169795 52 123 766337 78 87 959709 77 104 459060 109 147 425417 90 157 344889 10 138 688848 29 35 327169 23 170 613419 138 165 234247 56 162 335787 119 157 971791 103 143 31075 1 33 634218 67 145 335810 25 145 267592 6 72 603252 88 167 198292 74 89 218280 120 159 869383 37 113 662710 20 29 366516 20 62 800706 86 128 776231 150 157 95132 62 71 327710 45 76 900315 31 132 811735 32 83 174148 120 144 118005 7 12 42145 73 101 453907 33 43 939001 7 128 937598 44 112 84133 46 163 306366 43 87 687903 27 65 391214 43 139 449577 53 115 861444 63 86 906601 20 33 883626 12 165 660365 66 117 453620 75 120 793304 28 149 25090 106 133 995206 31 105 354378 89 107 452260 7 119 107609 93 140 226304 54 102 174844 34 98 631…
Output: 126934

Example 2:

Input: 701 3111 1 701 152 427 217989 88 451 483023 576 627 259498 616 696 203403 205 667 473331 207 701 885734 11 519 164069 625 632 594299 8 671 670090 172 505 391873 2 177 44598 124 200 778534 132 461 175481 542 568 598112 453 675 245749 336 629 580220 27 400 677324 53 262 64341 458 568 414501 199 598 649002 24 27 295914 338 507 705672 14 542 190476 467 663 553579 364 580 51278 308 624 549521 283 299 643727 156 499 659335 655 674 328171 403 534 207059 100 261 960922 500 682 738730 346 570 84638 255 299 509978 258 351 945490 564 671 876664 258 676 702454 271 285 489758 395 613 216327 154 260 180570 295 576 474320 291 303 253835 306 480 94665 38 144 914450 177 535 44916 31 617 716582 45 661 937861 290 677 112933 110 347 58047 192 639 490837 123 582 797260 225 512 777338 128 536 794061 142 319 887…
Output: 579604

Example 3:

Input: 250 686 1 250 40 176 626009 142 216 617918 174 179 134720 1 56 910388 195 239 232484 63 70 992552 109 243 641528 130 158 908852 227 230 193245 19 233 952563 169 233 83590 111 165 261376 147 153 9581 12 206 662807 129 219 851168 164 233 537590 70 157 220823 82 224 861331 21 220 393644 99 225 269652 26 75 229686 6 230 855160 64 232 849926 66 119 45744 43 224 307429 23 232 346186 36 155 430590 63 211 275634 14 205 675820 5 98 473906 204 216 831897 62 73 153131 125 199 623982 36 96 983370 28 76 187921 10 195 550916 75 170 734441 87 108 375831 88 181 340525 105 114 5458 4 223 592047 91 109 441457 94 158 484245 144 178 566760 91 207 483419 48 117 895314 76 107 20006 162 202 81282 140 191 678202 30 38 398172 1 55 182712 121 221 477197 23 75 438213 219 230 829417 92 209 265253 39 66 574912 65 209 …
Output: 945073

Constraints:

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

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