CT62325

Tracker's Ledger of bridges

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Before the gates of the coral atoll of Pearldeep close for winter, Tracker must finish the bridges 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 <= 1503; 0 <= m <= 4509; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 1472 1471 1 1472 538 893 91 127 256 970 53 1349 809 92 1137 977 103 1177 851 169 663 962 78 1453 493 705 1065 322 705 983 982 592 613 769 712 1353 578 1121 1385 298 442 1230 77 199 1433 657 832 1132 574 819 1013 192 391 533 366 329 833 774 531 1163 293 255 1055 978 37 616 480 994 1011 564 66 357 602 1020 1130 739 863 1320 325 375 1436 199 716 1092 729 858 1231 258 672 1385 475 924 1008 505 1237 1279 285 420 763 308 576 1283 847 442 721 246 235 981 664 94 937 36 68 788 417 32 1215 569 293 334 274 794 1158 930 259 563 877 985 1195 586 447 1142 215 96 731 244 17 112 3 517 884 927 434 1209 292 319 506 526 1162 1430 435 61 713 494 1012 1287 247 224 461 860 697 1196 652 618 816 930 265 1426 100 743 1189 967 1083 1352 961 415 680 504 387 1328 934 1001 1192 377 78 419 907 1224 1423 797 223 1104 58…
Output: 3788

Example 2:

Input: 1125 1124 1 1125 100 438 753 115 512 861 142 321 107 875 882 491 157 659 444 321 511 979 438 1086 878 1019 1022 636 2 107 604 31 248 566 586 831 540 644 955 896 615 642 647 614 1012 915 588 683 956 202 370 849 196 587 540 244 1109 565 186 632 939 183 199 291 818 972 691 87 1009 341 848 1083 799 23 543 282 689 941 85 73 232 343 893 919 999 241 331 746 162 868 406 334 739 521 329 1059 257 230 541 199 592 979 546 559 699 572 383 661 370 185 485 954 398 559 405 694 791 482 812 858 583 100 992 744 25 669 680 285 1039 368 355 1079 799 110 206 543 1001 1116 300 381 1097 657 526 756 171 9 142 55 528 691 414 22 511 82 575 844 128 24 356 512 85 915 410 235 1085 364 223 666 46 253 985 492 198 594 524 589 665 58 241 986 861 405 1105 17 699 724 354 777 952 437 359 378 315 305 768 255 732 898 816 448 75…
Output: 8662

Example 3:

Input: 105 4206 1 105 27 76 738 12 20 90 52 102 199 53 63 992 11 44 419 18 43 46 89 97 270 26 81 274 50 84 162 11 26 987 24 49 49 1 25 672 21 57 206 10 35 241 23 40 65 2 42 348 18 73 409 62 78 976 3 46 874 32 83 254 59 93 112 54 68 623 2 102 294 15 94 234 33 103 296 2 64 609 13 29 710 24 86 161 68 72 600 29 53 544 10 100 352 14 105 178 14 66 118 8 25 398 36 74 128 12 13 349 52 91 875 19 90 980 45 65 491 39 81 325 25 77 890 67 88 362 48 86 378 14 56 961 35 86 414 90 105 727 13 22 92 27 87 136 2 105 150 75 89 63 74 89 93 88 93 272 52 92 909 33 59 545 33 77 28 45 60 80 31 54 425 33 93 542 52 54 379 48 71 257 26 60 697 35 94 994 54 56 401 5 73 106 18 95 99 35 73 334 49 76 914 19 62 442 7 12 689 36 69 380 20 103 512 12 68 310 12 88 926 10 13 766 84 104 553 78 80 39 54 61 753 30 76 685 85 103 730 13 24…
Output: 118

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Tracker's Ledger of bridges - MEDIUM Coding Problem | CodeTikki