CT65025

The routes Fastest Route Puzzle

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

Jaya inherited the granary at the quays of Driftwood along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 828; 0 <= m <= 2484; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 6 15 1 6 4 5 869584 3 5 997107 2 5 748232 1 3 536755 2 4 592523 4 6 416770 3 4 347069 1 5 96252 1 4 714223 2 3 238217 2 6 80591 5 6 908037 3 6 972158 1 2 640911 1 6 402815
Output: 402815

Example 2:

Input: 422 421 1 422 174 250 208993 255 324 405991 23 208 19251 370 407 522623 126 313 852084 14 88 70446 65 254 675588 281 418 381967 125 328 663468 53 87 886275 50 152 139942 262 324 328939 60 253 158462 73 398 536267 9 235 269980 379 392 896831 272 389 54180 44 231 479346 98 283 495342 93 317 597822 55 414 604666 365 422 359927 249 321 49727 124 177 879540 154 391 849493 106 395 705687 50 186 381444 313 321 116027 343 412 368800 201 334 633204 132 215 996339 58 175 260193 59 192 751761 50 195 804693 120 264 547376 173 290 100703 76 108 731550 139 212 738974 58 162 556485 2 98 479856 335 403 161982 164 208 59254 5 92 793375 73 372 583525 38 344 768719 80 147 776247 62 421 120119 23 145 520960 166 224 693552 49 277 400827 64 358 291952 287 399 371222 89 266 341843 194 272 946770 317 380 490823 4…
Output: 3796311

Example 3:

Input: 569 1907 1 569 173 506 596129 4 443 146834 117 158 962386 314 411 40234 216 564 125286 203 300 133741 223 283 297102 36 189 976841 384 545 846929 302 540 176367 103 417 692837 29 506 254289 31 506 709477 32 560 269533 4 482 709699 174 345 162462 405 545 415700 74 268 424000 227 331 887649 114 503 826562 24 335 65211 337 526 716357 280 375 539066 191 378 91836 7 293 426653 47 87 240225 143 419 332980 426 568 186918 10 292 362906 239 305 991891 117 524 478928 353 383 621389 402 510 206037 106 538 442290 164 527 385550 375 379 371429 276 367 868818 22 311 276228 13 41 370872 329 394 488211 70 374 359453 96 104 141615 88 135 222501 114 565 907799 333 474 120851 415 558 581474 288 420 822457 79 293 671710 386 557 304298 399 471 163309 220 567 254997 10 184 619029 317 422 865286 115 427 521534 1…
Output: 825142

Constraints:

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

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