CT60437

The routes at Keelwind

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Caravans arrive at the shipyard of Keelwind with crates of routes, and Steward the clerk must account for every last one. 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 <= 956; 0 <= m <= 2868; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 299 2527 1 299 112 259 452 192 230 296 142 145 661 154 158 459 234 242 160 10 122 356 128 174 932 50 211 115 177 187 313 236 292 325 32 137 474 36 152 603 5 178 422 11 164 349 67 201 24 111 113 940 63 286 107 193 274 707 130 177 246 40 166 278 81 220 885 215 277 869 79 82 381 71 107 273 84 222 372 27 251 732 189 220 858 66 286 972 103 129 464 116 266 810 270 282 889 38 135 482 90 242 343 89 195 288 101 266 156 56 155 416 128 166 572 135 208 565 2 298 705 43 261 472 126 161 416 154 250 606 136 237 717 185 239 962 157 169 479 200 224 344 102 195 418 188 296 665 107 172 66 34 60 963 34 231 231 223 292 410 138 204 611 158 172 290 72 212 130 243 277 272 109 225 891 26 95 575 159 281 880 35 160 845 113 246 218 147 178 739 157 179 327 132 284 232 68 244 107 71 111 454 9 136 686 34 242 454 75 166 …
Output: 350

Example 2:

Input: 592 591 1 592 96 127 843 12 112 915 240 397 599 266 540 310 322 591 595 127 463 205 5 272 13 277 590 21 63 350 532 26 585 816 401 567 553 99 491 838 381 560 723 154 258 230 430 544 811 11 410 267 174 203 614 23 41 845 100 127 552 480 502 823 118 218 849 101 390 474 125 541 117 124 465 66 348 367 416 106 234 808 104 127 841 206 348 450 374 467 516 484 529 810 271 278 560 377 478 665 411 446 573 136 574 901 139 358 166 94 499 649 485 588 760 141 231 544 436 574 603 392 407 738 190 420 80 330 423 760 142 569 994 33 460 493 217 265 270 177 259 734 454 535 430 500 532 651 112 572 481 101 267 474 334 349 46 120 451 780 43 379 870 191 586 812 113 494 425 58 223 169 103 516 738 4 354 794 205 474 29 75 591 75 75 222 630 9 355 764 45 147 688 326 554 710 39 445 549 340 477 177 17 231 945 293 413 838 …
Output: 7710

Example 3:

Input: 381 986 1 381 97 162 921 160 163 214 26 154 617 194 204 486 26 233 156 212 289 697 39 146 805 293 342 749 169 176 33 143 171 740 295 377 530 165 289 705 84 200 565 111 323 936 271 299 600 20 332 456 35 381 860 301 321 443 98 299 477 145 206 615 71 230 519 95 232 5 286 365 892 44 336 267 2 360 358 180 358 374 42 97 588 40 132 422 103 220 948 161 218 444 65 138 715 145 353 60 36 275 52 187 348 442 41 371 991 9 337 60 222 357 177 177 287 293 73 271 268 207 271 720 117 146 6 299 319 660 255 310 461 30 218 389 67 146 69 9 358 523 92 264 730 54 316 409 7 217 96 242 378 170 92 225 780 2 357 135 74 281 809 241 253 245 40 340 620 205 339 192 175 330 907 112 279 416 136 187 980 183 302 364 110 234 631 61 360 477 6 106 130 73 119 9 83 136 189 92 381 517 94 274 365 162 235 235 219 264 963 232 293 942 …
Output: 1514

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
The routes at Keelwind - MEDIUM Coding Problem | CodeTikki