CT51451

The corridors at Glowfen

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Every season at the lantern district of Glowfen, someone must file the annual report. This year the task falls to Nila, armed only with the corridors register. 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 <= 1708; 0 <= m <= 5124; 1 <= s,t,u,v <= n; 0 <= w <= 1000; distance fits 64-bit.

Example 1:

Input: 419 3296 1 419 248 373 476 180 344 52 320 419 490 35 249 992 261 373 124 40 41 40 117 395 445 233 255 577 141 201 212 270 398 898 293 391 614 288 358 902 2 136 226 337 418 50 362 368 905 84 396 347 95 306 929 347 361 771 3 82 321 200 408 174 204 262 66 91 195 129 71 365 651 8 274 486 59 354 239 325 415 779 57 376 841 47 69 742 15 34 916 126 131 723 143 238 408 181 223 441 49 303 496 195 199 188 154 162 764 34 347 584 58 272 383 90 408 716 79 270 533 177 311 805 17 381 682 26 188 557 9 224 199 209 213 458 89 376 695 100 135 960 24 70 238 79 220 412 66 328 828 42 117 118 51 112 895 239 287 126 313 387 204 2 204 861 137 191 365 267 313 756 20 404 110 174 323 775 11 108 699 125 340 569 60 386 566 73 312 883 297 356 111 187 324 226 364 411 556 222 389 778 273 323 741 352 369 61 72 141 35 107 11…
Output: 388

Example 2:

Input: 168 2967 1 168 59 165 656 58 94 697 45 129 916 116 154 788 104 130 895 3 95 649 76 145 698 137 138 515 62 92 2 65 134 736 44 94 306 36 158 538 46 132 698 92 101 547 59 109 232 47 150 329 91 122 274 63 163 585 111 150 722 109 123 333 68 77 807 1 90 724 127 152 238 63 109 282 23 118 197 59 114 452 121 127 262 5 161 688 116 152 184 3 56 241 91 141 936 34 136 745 11 54 753 105 125 229 116 135 294 4 62 623 30 119 290 28 98 511 87 149 464 10 139 303 11 139 623 40 66 540 93 99 914 57 68 761 33 158 580 46 157 446 37 136 623 94 119 379 40 119 925 50 56 676 64 144 2 19 130 97 135 157 900 123 135 803 13 104 499 63 90 471 25 47 232 38 88 14 45 66 109 15 89 991 162 166 114 76 144 357 14 118 91 46 166 914 36 118 709 100 132 303 82 129 234 127 146 68 54 140 955 60 123 140 72 168 374 69 144 552 26 51 657 …
Output: 215

Example 3:

Input: 1033 4101 1 1033 218 838 700 768 770 795 778 817 415 109 371 696 329 683 550 541 689 34 434 794 40 517 719 799 131 904 505 445 453 660 339 798 487 394 762 306 360 896 287 793 976 960 32 897 734 487 502 352 516 842 922 337 636 462 330 1001 179 837 897 981 799 929 722 21 827 34 6 352 433 7 337 692 363 873 914 27 618 587 103 750 588 52 543 582 470 931 499 179 386 497 221 967 110 221 701 996 333 912 655 121 518 549 292 701 232 792 808 553 365 471 685 508 623 50 262 275 71 163 917 708 680 1029 394 17 247 877 661 867 482 64 531 368 22 932 584 40 925 944 67 797 799 609 797 889 388 449 794 744 1013 337 145 771 934 462 818 44 292 722 977 355 983 674 203 519 893 204 388 722 221 326 604 115 857 292 188 701 646 708 884 787 208 677 504 400 753 184 278 911 662 380 513 15 277 410 43 200 255 627 114 755 5…
Output: 1339

Constraints:

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

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