CT48342

The Fastest Route of the Celestial bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rekha the store warden watches over the quartz ridge of Glimmerfell's stores of bridges. A careful computation stands between order and chaos. 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 <= 1332; 0 <= m <= 3996; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 475 750 1 475 116 381 771475 181 387 330326 42 263 859168 105 380 485152 293 339 151985 256 418 105520 106 472 42664 332 423 310170 37 470 369182 138 369 259304 51 444 484789 295 322 987710 32 215 448884 33 390 121236 210 409 615697 93 220 629617 34 227 557190 46 270 860679 13 387 812633 103 250 857528 452 474 68031 185 242 944169 180 397 106625 163 295 761924 333 429 360727 195 359 675769 64 291 53607 321 362 975069 11 153 177877 27 422 210558 225 322 581317 308 342 32093 85 443 690283 206 336 211431 231 452 96426 88 408 945773 117 341 809761 195 309 501231 21 472 556854 139 255 638264 77 469 52219 136 369 524798 301 311 992658 85 444 659674 131 322 21127 185 418 861873 5 256 913394 362 424 705898 326 417 913648 17 152 304463 382 389 51457 54 69 505977 301 427 479699 172 308 660915 105 15…
Output: 2508533

Example 2:

Input: 947 1336 1 947 718 933 790458 170 402 82291 433 447 383272 216 842 787264 531 643 497071 543 803 760065 377 832 857011 567 885 862660 271 587 518217 376 707 252391 809 818 623503 2 912 125736 3 550 89169 569 841 784322 190 751 311249 234 715 496956 515 724 754208 242 908 564658 127 737 213551 770 877 786705 137 573 180467 868 891 550514 340 488 400213 11 70 7344 372 734 327945 67 99 223634 422 455 502119 565 706 936678 346 859 15278 753 853 700869 113 475 489740 274 614 857272 341 869 423766 497 534 952645 133 330 112151 153 366 435050 224 299 238280 114 439 691328 426 662 618239 69 380 202908 54 678 305220 256 813 667575 104 322 865050 31 109 410692 482 646 433707 32 367 239687 179 239 22863 331 408 250571 569 798 382683 174 371 559366 251 714 598998 544 611 567107 18 102 823739 491 665 8…
Output: 3387818

Example 3:

Input: 723 2625 1 723 70 677 851480 427 464 854134 481 602 308752 470 634 774726 134 221 443502 156 700 222756 300 346 188889 246 585 843044 18 532 664081 423 439 515157 257 383 358954 190 489 258593 135 700 694822 473 494 310776 438 500 284017 426 515 563422 462 608 857343 144 652 437839 163 260 543769 183 198 348808 362 570 781528 438 567 78377 137 646 815193 108 576 217875 116 158 155814 317 675 16506 126 531 893767 467 644 380945 295 438 645547 314 609 585827 232 599 491752 598 648 400736 115 682 263881 29 469 889454 241 497 402207 254 347 77817 147 308 959017 211 519 197054 553 659 281534 265 717 754039 111 197 418639 133 297 36007 100 716 671643 287 367 913043 7 494 364893 52 634 32491 576 601 458517 380 428 462639 619 626 568307 574 722 872452 482 596 643138 235 597 525920 382 563 885782 2…
Output: 867992

Constraints:

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

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