CT64429

Jaya's Fastest Route Ledger

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The dispatch writer Jaya has been asked to restore an old family record. On the desk lies a long table of bridges 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 <= 816; 0 <= m <= 2448; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 364 2349 1 364 16 303 57 110 342 613 42 179 702 126 214 922 249 251 344 56 292 885 208 335 943 264 309 809 202 254 140 107 314 29 45 188 233 49 281 253 57 167 902 330 334 97 74 184 939 309 312 571 145 190 611 298 309 296 121 254 527 44 57 655 191 231 771 32 104 680 261 302 575 98 302 389 41 312 112 9 60 978 229 302 914 54 264 689 44 297 380 205 338 337 217 273 929 30 196 706 54 311 36 150 248 253 16 319 672 310 329 46 267 302 452 185 311 190 154 281 165 218 297 321 279 310 644 91 340 144 108 225 761 14 277 747 3 222 529 256 291 13 4 219 3 236 338 646 7 51 841 1 83 467 2 346 75 62 178 122 68 82 906 171 361 347 14 323 642 11 141 206 166 333 249 23 318 349 95 152 105 307 358 984 146 247 948 78 284 74 193 248 645 28 127 794 70 335 49 47 345 611 42 241 218 4 324 4 85 257 940 114 328 523 47 212 …
Output: 771

Example 2:

Input: 336 335 1 336 45 270 423 93 333 992 223 271 322 24 73 831 75 288 913 119 313 97 238 277 88 117 307 486 277 303 558 37 41 654 25 224 983 194 318 84 78 235 930 59 196 858 118 336 468 163 322 322 1 3 600 37 119 53 37 212 309 181 291 693 192 240 143 26 252 767 84 294 814 248 270 884 239 261 277 8 285 312 5 206 295 61 236 134 118 175 362 14 288 960 187 221 364 87 102 51 140 158 102 33 315 745 60 245 93 27 305 469 28 248 497 167 201 477 8 91 345 171 300 801 161 248 51 116 239 340 89 149 17 85 247 89 7 150 198 243 331 435 42 90 823 251 324 517 99 179 451 51 130 235 204 251 381 47 116 956 104 114 270 115 214 58 96 207 973 131 151 378 94 187 976 32 312 457 133 145 993 54 148 163 126 188 667 110 130 552 61 332 652 64 116 911 36 42 400 19 139 851 116 335 198 297 326 206 113 261 438 169 333 99 186 228…
Output: 4053

Example 3:

Input: 312 605 1 312 107 212 748 67 292 221 64 198 923 154 200 956 5 299 354 78 102 736 46 131 10 69 133 913 9 288 328 85 100 707 166 287 835 28 145 151 21 244 436 9 283 316 93 103 719 1 84 703 8 226 243 86 116 208 21 279 125 56 183 998 171 261 516 223 239 681 150 250 112 57 132 824 39 121 596 71 236 701 144 161 110 1 185 896 116 267 293 30 97 187 82 214 537 87 194 792 92 287 684 11 188 534 63 201 769 29 59 912 213 293 858 61 181 781 194 288 43 129 235 11 99 196 832 70 236 527 136 292 223 38 205 718 74 274 253 102 179 14 44 162 617 13 262 776 211 275 293 10 254 771 48 307 181 68 90 208 17 233 941 17 162 689 7 83 211 89 225 172 125 287 327 181 302 20 166 240 63 257 300 405 18 150 760 89 152 95 104 109 149 224 226 128 19 71 297 115 128 334 281 288 183 7 147 26 94 183 9 207 271 851 61 213 746 193 30…
Output: 1682

Constraints:

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

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