CT54216

The bridges Fastest Route Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

At the jade shrine of Serpentis, Cressida records each bridges in a worn leather ledger. The guild wants answers, not guesses. 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 <= 1694; 0 <= m <= 5082; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 1379 2671 1 1379 133 178 697 1057 1279 894 607 785 385 1148 1192 535 844 1180 833 825 1171 406 92 404 389 1337 1344 916 751 1232 258 825 953 334 590 939 835 874 1377 86 759 1205 787 931 1157 897 532 605 789 569 880 814 362 1301 441 180 488 737 317 617 937 284 484 908 971 1049 718 826 1363 822 13 287 309 94 1170 100 199 442 786 1036 1152 339 444 990 254 233 1376 100 957 985 987 187 1317 627 444 1090 26 539 1308 273 1111 1155 597 629 746 846 336 641 590 21 518 887 83 1355 409 342 1118 335 509 1248 89 857 872 534 673 750 584 437 496 842 47 293 315 826 1067 835 982 1093 961 13 678 335 1173 1269 961 1133 1326 535 690 787 876 366 914 977 428 1257 421 814 1361 123 789 887 367 563 950 237 1013 1350 754 259 383 908 268 694 205 563 932 547 238 916 457 697 722 775 107 706 708 676 940 957 65 878 339 6…
Output: 2340

Example 2:

Input: 1181 1180 1 1181 1066 1105 572 287 899 686 28 494 259 471 1145 36 538 550 148 325 1051 553 643 1042 319 719 954 925 715 1138 575 308 765 109 362 630 247 490 886 535 431 500 343 1062 1088 853 187 1058 588 87 198 793 279 1038 745 193 246 419 284 679 129 474 1153 76 695 835 678 871 1144 676 486 537 561 29 780 192 989 1111 431 334 1161 287 635 812 741 186 682 68 161 610 317 437 604 673 394 1157 415 136 1122 945 485 492 180 614 617 534 1107 1160 112 90 424 514 471 1010 123 472 1120 87 22 822 320 415 620 936 137 521 726 318 338 152 81 726 697 123 574 874 786 969 782 40 718 324 116 975 916 355 1061 858 538 1111 752 173 665 558 396 435 99 171 690 185 598 748 904 740 1123 763 968 1099 510 455 801 294 306 649 995 242 613 66 691 803 53 354 1040 712 656 681 276 187 809 446 541 771 177 166 934 994 306 …
Output: 4048

Example 3:

Input: 699 868 1 699 234 688 185 413 539 456 481 620 565 403 505 549 218 352 855 19 362 986 390 397 315 277 448 696 573 630 342 538 633 833 380 439 891 319 492 115 247 589 613 7 331 724 367 483 909 13 139 650 208 324 271 59 617 686 73 360 298 226 331 332 46 75 676 335 697 250 151 555 94 32 43 285 19 426 645 114 126 787 529 575 373 429 682 874 120 668 96 182 430 761 220 366 6 303 612 717 17 572 444 268 358 370 344 588 119 185 237 346 2 683 533 144 515 959 267 478 305 600 670 258 167 690 355 36 441 800 114 138 935 243 603 894 510 618 439 18 587 328 95 265 851 638 639 630 278 639 461 194 273 72 241 610 406 257 391 894 188 192 384 489 658 475 514 664 139 310 469 321 255 370 661 207 223 290 24 664 766 102 498 273 330 689 710 250 568 876 268 408 360 108 616 184 468 579 164 95 250 349 153 239 276 101 42…
Output: 4063

Constraints:

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

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