CT46450

The Fastest Route Beneath Crowhaven

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the rookery of Crowhaven; Mira weighs the day's corridors manifests and starts the calculations. 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 <= 1602; 0 <= m <= 4806; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 969 2180 1 969 16 178 719 209 844 37 344 380 620 375 819 285 154 515 694 297 732 102 465 786 595 644 673 329 336 746 370 277 827 431 763 831 771 318 431 227 17 554 167 67 676 388 81 872 436 101 500 79 523 770 907 294 504 739 433 545 629 572 857 65 704 894 17 319 426 362 825 885 200 156 738 66 409 813 582 808 889 4 719 881 272 27 438 233 401 918 786 121 287 473 216 934 171 242 270 490 421 836 652 233 858 842 558 808 648 173 698 625 339 843 760 648 725 208 50 830 781 65 361 551 305 726 549 120 144 293 269 616 402 227 399 478 198 898 549 242 790 527 170 669 119 130 356 932 391 533 67 98 246 991 203 470 177 535 576 367 146 615 609 16 637 215 221 481 227 748 917 138 538 541 910 510 647 890 30 178 82 16 655 969 144 397 651 537 651 943 533 894 166 808 962 917 432 611 479 303 618 982 430 559 739 5…
Output: 2277

Example 2:

Input: 650 4391 1 650 125 135 281 54 503 80 418 456 152 50 168 569 43 432 894 125 146 932 226 372 980 317 503 80 161 431 554 316 581 616 10 522 574 49 287 985 98 221 953 280 502 806 10 586 66 71 275 125 212 437 185 307 538 191 455 596 717 183 437 334 248 315 42 26 58 847 271 563 75 235 571 139 263 609 382 16 266 64 501 613 729 400 631 490 180 269 345 470 522 192 49 183 506 418 499 963 318 544 817 274 644 795 51 357 908 51 220 602 139 277 396 60 467 665 195 579 990 15 231 935 28 423 980 80 485 468 346 513 757 22 536 44 428 511 646 177 627 874 185 191 721 531 564 689 334 481 393 37 170 852 177 259 767 247 540 979 118 404 719 108 220 228 289 379 174 73 526 545 58 187 122 175 316 730 346 467 113 61 452 786 319 522 945 429 438 307 106 635 119 104 231 606 437 571 617 256 331 152 31 385 357 382 622 362 …
Output: 598

Example 3:

Input: 758 2714 1 758 263 433 410 349 699 219 133 638 419 104 342 306 64 714 742 242 342 620 576 664 750 595 723 751 502 670 317 565 632 992 95 422 855 643 687 179 408 566 925 221 674 420 492 716 900 206 380 949 310 556 554 556 678 137 372 734 122 130 222 875 217 307 285 182 592 823 37 572 255 455 716 456 445 521 125 82 683 553 531 617 637 148 165 692 56 478 993 35 398 61 86 102 170 26 273 972 106 273 673 133 161 100 166 220 61 200 700 87 287 479 386 78 141 47 28 537 841 443 569 222 319 437 788 81 158 915 458 669 821 1 662 791 345 479 80 542 631 421 19 251 995 486 500 521 122 740 368 191 222 817 538 675 727 131 271 132 245 491 59 99 555 443 54 176 151 534 554 914 417 425 933 458 539 140 460 492 787 280 382 339 30 250 482 519 667 143 392 492 336 109 747 311 449 728 164 115 328 988 89 753 479 308 5…
Output: 866

Constraints:

1 <= n <= 1602; 0 <= m <= 4806; 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