CT58811

Miller Counts the tunnels

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The auditor Miller has been asked to verify the ledger before the auditors arrive. On the desk lies a long table of tunnels readings. 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 <= 1331; 0 <= m <= 3993; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 171 1071 1 171 122 150 477627 53 121 495233 69 150 307006 95 96 753659 15 130 212401 1 150 419590 23 92 959336 58 171 477558 1 170 336270 51 111 149326 77 90 89062 29 112 557516 76 140 465533 48 97 473215 107 165 922600 20 124 796090 118 160 51988 93 129 588500 9 93 71173 4 105 804149 57 92 19567 108 142 772667 15 118 799675 35 171 323761 34 35 162483 17 67 847395 67 114 170069 4 59 262268 10 28 125218 28 42 860546 51 85 320206 58 169 104861 70 90 653151 39 107 540827 64 108 516128 28 36 762758 36 143 303990 84 105 809050 10 84 481777 83 94 400683 103 161 661742 9 77 71559 3 65 780483 90 129 424631 72 78 830616 116 149 139238 56 159 609413 112 137 286643 86 119 76228 66 88 221112 63 152 682476 33 55 198630 45 117 712745 75 121 115194 107 151 725021 17 107 475939 40 145 7652 12 13 574074 19…
Output: 885902

Example 2:

Input: 176 3283 1 176 82 115 826348 47 109 51209 151 156 601674 48 96 607458 109 150 57914 83 95 35749 40 82 705649 125 175 987510 69 139 177712 84 169 113267 81 175 48615 140 158 448167 49 68 891823 79 120 346047 12 139 330241 70 150 517452 128 175 758617 8 141 746260 22 46 335893 52 147 239623 76 125 264346 57 132 769921 76 173 81335 55 133 496279 31 40 307543 109 161 599583 51 143 928552 21 68 451708 19 90 499636 78 117 968880 4 61 196967 64 110 172452 79 165 290327 45 55 836264 25 138 178059 9 65 620700 56 141 597397 36 58 928452 45 107 162129 67 175 802599 79 163 759017 89 113 632854 14 117 698157 38 85 257179 118 145 452273 49 90 198153 74 159 383981 128 163 132692 129 136 971186 78 150 701657 16 109 468404 47 114 624920 81 112 610028 52 117 872064 5 33 304784 60 62 875677 43 126 47986 51 8…
Output: 215150

Example 3:

Input: 924 923 1 924 51 119 288944 13 756 599782 85 162 838361 288 738 994949 45 134 745221 615 818 419334 57 838 806876 120 607 442681 641 904 817119 613 821 564444 335 531 341025 738 753 939853 57 575 229928 836 866 619777 115 743 444890 37 851 933727 24 459 129154 36 921 293731 457 631 568144 387 829 920942 193 234 103172 400 565 170469 22 481 68859 311 608 200582 558 685 320957 111 246 814404 691 786 598685 219 296 845936 418 857 953013 124 135 662648 161 362 557461 201 633 88540 189 872 256724 20 648 97915 730 827 875353 178 584 665548 624 783 115942 787 924 503230 166 873 71200 283 806 227499 324 372 965710 242 795 747274 82 688 875448 329 390 422697 547 898 523013 396 818 649937 329 696 766866 293 299 633080 79 574 691339 428 918 354316 26 127 960673 29 490 641886 42 571 720532 875 911 216…
Output: 2494559

Constraints:

1 <= n <= 1331; 0 <= m <= 3993; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Loading...
Test Cases:No test cases
No test cases available.
Miller Counts the tunnels - MEDIUM Coding Problem | CodeTikki