CT52945

The Fastest Route Beneath Crowhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the rookery of Crowhaven close for winter, Nico must finish the routes ledger - one figure at a time. 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 <= 1010; 0 <= m <= 3030; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 119 119 1 119 11 95 1000 79 90 748 71 99 257 81 107 507 76 115 799 1 64 836 3 112 464 32 36 457 47 65 452 26 90 62 102 118 716 52 56 74 48 109 116 13 112 664 55 68 969 43 85 83 47 100 376 53 75 173 89 101 998 87 113 323 65 118 402 75 100 560 42 54 683 16 43 988 15 22 190 15 70 944 21 107 450 35 54 756 6 115 961 11 32 530 18 82 301 18 45 884 20 31 338 57 94 454 1 30 722 18 97 154 21 101 669 85 101 700 65 75 955 28 110 416 24 86 685 12 66 219 59 66 695 33 91 335 96 113 940 32 111 160 30 37 129 44 70 953 50 63 253 38 47 544 9 15 515 25 30 826 98 101 567 6 50 664 71 101 169 20 34 497 77 114 232 80 118 855 84 97 740 19 36 190 2 94 290 21 65 523 9 59 906 73 100 294 21 39 814 30 45 80 28 91 674 62 85 519 1 78 84 4 103 87 52 87 520 15 28 936 8 75 530 69 107 413 41 99 896 53 108 506 35 97 236 60 61…
Output: 3905

Example 2:

Input: 223 1946 1 223 122 157 426 176 185 162 68 106 730 3 29 500 53 142 491 52 66 959 120 207 839 88 173 330 21 189 711 21 120 161 52 211 964 108 208 985 86 198 673 146 150 805 36 101 117 43 195 622 124 219 290 90 198 87 56 185 221 13 126 998 63 196 905 30 149 950 180 205 142 26 32 797 87 124 773 114 153 430 5 81 972 111 158 781 50 75 289 65 68 391 18 134 22 15 107 988 200 219 436 82 154 383 30 155 510 16 86 285 183 199 119 40 64 157 82 146 190 83 141 145 6 37 566 189 196 242 73 146 532 33 198 730 57 102 571 7 53 87 36 142 850 46 166 960 6 125 444 34 93 15 20 143 698 11 19 199 88 175 9 86 217 71 12 212 90 64 139 881 43 212 547 65 163 588 51 107 435 74 79 307 91 99 569 129 214 558 143 171 375 15 220 401 68 212 59 105 165 486 10 16 714 9 181 566 39 87 620 61 85 852 62 139 64 130 146 804 70 153 316…
Output: 321

Example 3:

Input: 759 1956 1 759 271 565 660 335 556 688 108 750 98 175 535 403 299 426 357 63 181 755 162 753 815 195 686 150 52 199 697 158 436 122 445 483 53 3 102 854 281 757 489 436 587 139 76 648 112 15 198 579 649 746 923 437 561 285 479 743 160 421 689 550 78 735 538 172 453 65 103 468 944 208 714 155 108 648 561 231 617 452 129 206 411 243 669 305 225 619 110 33 401 288 135 683 220 162 517 640 169 306 929 17 376 913 3 136 863 664 733 984 3 160 737 64 465 93 589 693 843 195 320 969 180 595 192 170 214 770 22 709 172 17 225 124 654 698 882 380 758 38 58 222 985 436 709 15 433 553 618 235 672 860 321 717 208 66 357 545 586 715 592 426 606 65 295 665 273 224 284 991 10 11 618 46 657 686 123 607 871 42 77 162 99 557 494 65 482 99 512 756 360 168 650 524 258 674 439 237 662 60 345 533 273 348 382 235 362…
Output: 1212

Constraints:

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

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