CT60305

The Lazy Fastest Route

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Lothar the inventory keeper watches over the gull cliffs of Screech Point's stores of routes. A careful computation stands between order and chaos. 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 <= 864; 0 <= m <= 2592; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 208 207 1 208 61 205 943 45 194 461 160 179 31 21 129 561 47 159 456 8 190 441 70 115 959 57 207 85 106 158 935 186 207 447 37 150 825 85 168 617 79 97 248 18 152 804 144 188 130 51 147 267 22 157 621 112 129 96 1 126 461 36 145 528 59 103 513 118 198 863 141 167 909 58 204 334 69 170 336 54 129 496 35 111 565 100 131 921 89 139 116 96 208 210 161 170 154 15 181 572 130 151 725 3 148 742 13 78 241 156 158 533 191 195 920 170 192 890 24 181 776 7 197 884 26 63 857 42 72 823 176 195 251 43 199 598 16 124 154 49 152 847 69 155 265 66 74 768 105 160 349 124 199 125 58 160 379 36 110 771 120 139 12 19 39 304 25 46 649 5 99 621 35 50 87 122 183 263 111 196 502 123 134 955 46 137 681 133 145 344 114 149 328 44 54 285 98 185 511 93 182 44 97 127 451 111 124 925 57 142 651 163 166 407 82 127 356 12…
Output: 3198

Example 2:

Input: 36 630 1 36 27 36 126 1 32 131 20 36 156 9 31 690 11 29 712 8 31 181 9 18 700 2 9 78 2 12 485 27 34 959 30 33 147 2 23 750 12 32 974 8 19 727 3 8 717 17 20 844 6 10 521 7 10 513 2 13 357 4 9 617 7 9 705 10 20 255 5 24 565 3 29 262 13 33 305 21 22 978 22 35 362 19 30 751 11 24 668 8 14 851 17 35 917 31 32 448 7 29 676 8 11 282 10 29 683 4 21 904 28 29 83 8 35 638 2 6 317 16 23 620 16 22 328 12 24 993 1 36 933 17 27 730 9 36 169 4 34 195 25 32 896 29 36 460 10 16 6 11 20 372 18 26 642 19 31 441 30 32 722 8 26 751 30 36 70 28 35 176 14 25 708 7 15 22 13 20 110 23 28 336 20 35 412 22 36 263 13 27 39 15 17 94 1 13 619 2 18 686 5 27 776 11 21 217 17 34 710 22 29 978 17 29 686 10 17 973 17 36 128 21 30 960 20 34 147 32 35 425 4 12 14 16 30 124 7 22 466 1 28 844 16 32 526 24 30 673 12 33 730 4 14 …
Output: 76

Example 3:

Input: 793 894 1 793 231 365 275 369 536 362 3 229 714 189 342 951 52 60 544 70 350 32 74 332 906 11 774 545 589 706 2 217 776 8 81 330 264 371 679 757 563 633 775 671 710 812 226 292 459 164 291 635 225 510 797 67 425 807 282 764 615 229 481 736 73 712 637 291 550 246 632 758 13 163 698 882 29 233 928 486 671 916 582 644 139 640 734 580 688 735 977 396 456 588 562 742 748 1 276 660 84 771 384 236 287 189 249 290 749 591 605 159 63 764 171 544 719 760 150 766 271 100 477 814 52 479 114 685 765 521 167 424 860 507 621 372 194 334 882 394 558 183 283 297 711 589 738 111 230 367 617 33 562 601 45 431 867 484 755 651 413 729 164 80 168 993 320 350 16 125 630 192 110 784 72 458 658 864 95 662 508 90 288 440 294 397 264 95 305 121 369 483 182 544 662 288 209 463 665 296 545 445 285 301 908 419 773 672 …
Output: 3738

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The Lazy Fastest Route - MEDIUM Coding Problem | CodeTikki