CT49826

Chandler's Northern Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the mangrove channels of Rootwater opens only for a perfect tally of routes. Chandler means to find out. 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 <= 1088; 0 <= m <= 3264; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

Example 1:

Input: 640 1286 1 640 119 187 109528059 287 416 635107939 24 517 43672929 409 640 238076950 125 154 479066014 418 467 908502614 342 584 190007696 138 249 146771278 133 154 213759665 272 606 344540369 411 624 648981782 381 588 330969050 74 243 450941797 132 439 923544811 178 321 499384217 351 470 993496756 1 578 810385725 152 412 89038290 407 527 46301718 315 415 744291958 16 575 824936457 91 596 541585737 20 458 776680759 291 487 621593626 9 394 684239779 265 620 749239314 140 261 182441270 182 326 137921826 350 508 274817488 143 552 470077848 394 603 481918579 1 34 672141222 492 602 916694933 249 627 573821349 120 596 877409204 90 417 689795364 263 503 998164885 387 561 874576934 41 544 50025309 87 324 867284618 59 308 929379087 127 351 273807391 190 403 388912757 13 541 24357766 148 399 6233834…
Output: 979468042

Example 2:

Input: 1008 2831 1 1008 160 524 720355543 227 531 178299769 418 536 378706920 378 978 720359088 446 490 102537620 59 296 903703915 541 653 947868376 111 216 305485572 754 978 596461279 629 685 666959404 22 804 391086643 628 906 696263595 60 794 388148699 193 284 257710139 5 381 804584097 443 765 551084889 214 401 997643009 397 833 183566038 981 986 148236732 147 246 929836681 9 959 992080618 147 966 349604985 673 732 710310876 14 441 101347600 657 948 765930479 183 317 212081121 158 419 815445786 490 616 834440023 86 300 429957370 536 704 946248043 65 388 70700120 666 710 827914588 37 581 579587880 107 159 586107525 408 557 793669946 452 977 745669822 894 983 697528971 749 791 800917532 626 683 136647316 572 879 194272652 542 597 684619636 69 114 855347807 366 716 329916401 774 983 152017822 141 …
Output: 1587184902

Example 3:

Input: 578 2700 1 578 116 565 37962634 165 491 667060729 241 459 95013343 148 457 343568393 167 401 456670356 205 459 6929387 360 477 554925349 156 214 301850750 234 432 89464267 106 181 295511483 250 473 904300225 247 304 271448201 32 90 295456957 65 159 329550140 98 550 859441199 65 176 459822347 30 249 634227588 123 409 687269685 252 537 721663206 240 327 334690120 233 548 256291998 32 203 657342211 83 132 700522787 224 425 25203040 254 257 8335448 81 377 590050587 179 494 18207558 525 535 294096374 396 488 194965023 121 189 764242344 58 90 512440453 371 408 625186437 18 346 223669687 320 349 995446412 100 235 918943585 47 543 285671935 44 327 910068522 202 366 794010270 337 344 806342983 89 422 370679782 260 286 194529181 322 404 746420103 319 414 245742400 133 198 185084291 341 389 354705266…
Output: 932291696

Constraints:

1 <= n <= 1088; 0 <= m <= 3264; 1 <= s,t,u,v <= n; 0 <= w <= 1000000000; distance fits 64-bit.

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