CT63465

The Fastest Route Beneath Needlepoint

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the pine barrens of Needlepoint; Kavya weighs the day's tunnels 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 <= 1589; 0 <= m <= 4767; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 910 909 1 910 348 847 679 446 585 464 488 839 235 200 436 46 47 685 251 44 313 791 83 246 778 105 850 543 283 315 404 785 816 184 350 623 83 358 608 472 246 417 182 653 863 395 150 356 555 330 511 698 7 315 835 9 703 313 541 646 10 567 861 375 583 862 325 99 651 800 549 551 962 66 338 248 128 606 852 5 151 521 16 845 915 73 681 998 63 210 57 219 881 392 85 350 965 212 896 303 248 851 252 145 842 274 424 700 692 725 840 568 594 799 606 366 681 910 144 408 619 537 564 486 300 563 511 628 635 240 245 678 451 549 731 297 306 596 951 392 687 83 51 317 399 327 644 802 88 526 49 5 886 713 26 857 580 94 814 1 777 855 530 481 610 85 541 774 258 610 793 505 810 851 87 43 532 683 352 776 522 57 552 870 341 380 731 475 740 788 287 508 180 456 683 819 593 697 733 164 391 540 171 566 246 490 633 512 148…
Output: 5457

Example 2:

Input: 873 2517 1 873 308 336 421 190 322 390 166 452 77 515 530 576 36 581 735 640 769 874 409 476 631 317 463 92 210 643 195 727 869 814 319 709 28 530 743 163 96 493 437 456 775 779 359 378 474 14 665 494 685 765 380 337 680 319 441 628 314 428 719 490 316 364 972 570 807 987 231 566 616 69 199 282 283 737 304 436 450 302 344 659 961 262 476 768 228 502 694 456 873 296 2 506 6 504 664 862 349 357 319 34 816 742 185 233 671 381 725 173 18 744 404 352 690 974 594 683 809 328 629 286 387 845 334 658 696 899 132 571 368 720 843 24 394 777 814 488 872 189 77 194 257 117 302 344 427 567 579 11 413 989 211 554 839 173 797 699 82 248 929 549 747 284 479 598 747 226 648 756 665 687 714 532 686 103 103 252 264 93 837 177 222 272 164 568 798 128 160 728 965 115 394 590 338 721 508 39 364 63 51 218 940 34…
Output: 1266

Example 3:

Input: 1160 3599 1 1160 235 1011 761 669 1088 13 86 276 857 613 963 764 87 1034 547 694 853 772 36 214 734 199 854 304 2 1030 404 41 400 41 16 278 540 50 407 480 513 586 266 1148 1153 347 518 816 85 164 985 464 275 710 435 194 509 594 68 232 490 388 501 189 384 924 846 722 958 711 351 932 769 75 510 243 346 851 1 235 690 615 626 732 901 739 1130 257 314 686 448 244 801 505 70 956 636 121 889 665 1097 1100 510 556 782 83 819 885 39 154 695 727 34 722 297 34 1160 228 202 545 986 268 472 249 274 510 611 13 99 866 422 1075 256 598 767 999 114 618 80 411 564 659 345 895 909 375 620 348 680 1062 289 824 1054 976 1035 1125 344 319 863 574 194 1149 830 226 925 124 198 332 609 608 732 741 519 574 288 871 998 712 25 428 357 40 608 586 231 1006 375 218 875 986 417 952 690 987 1000 425 76 803 975 751 1048 17…
Output: 1312

Constraints:

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

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