CT58543

Darian's routes Reckoning

MediumL6 · Pointer PhantomAcceptance: 0.0%XP: 100

The harbor bell rings at the galleon yard of Masthead; Darian weighs the day's routes manifests and starts the calculations. 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 <= 1268; 0 <= m <= 3804; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 1196 1195 1 1196 634 976 236275 414 669 730138 785 1132 649891 120 1060 695505 73 233 294633 2 513 357675 611 634 518310 323 465 138972 183 1078 339619 4 725 838329 528 937 582542 704 1090 31531 900 1052 56992 646 848 32282 630 949 954535 214 648 742502 230 560 29992 661 1087 485975 95 722 121340 968 1078 32514 261 317 728914 84 871 38019 147 261 177767 258 387 549587 652 1117 823788 322 1159 622518 905 1068 279511 656 1056 568436 161 1182 176648 276 377 561518 431 1122 113481 145 244 467886 542 1008 398686 687 850 303872 811 820 5218 11 1010 347651 579 774 714403 65 279 549225 274 422 490401 246 366 615368 478 697 321741 299 472 916424 175 610 829853 447 856 195526 805 920 478582 108 483 674605 434 822 357402 356 921 907102 324 969 57003 415 893 374847 195 324 41810 330 579 69308 323 580 …
Output: 2292602

Example 2:

Input: 800 2870 1 800 133 406 389143 467 587 247349 18 469 526831 353 682 974169 307 800 517929 533 621 321750 237 407 175078 529 600 439569 395 481 78060 77 396 459499 347 522 129670 209 710 425610 169 345 150853 148 236 904672 465 730 184422 483 639 922467 259 260 738270 114 566 965928 273 650 80923 598 681 891176 496 646 423044 22 660 35741 182 371 49044 493 736 933666 479 598 630484 475 523 892154 463 501 831556 705 782 224313 36 743 564700 196 765 919551 592 692 488458 299 395 842122 166 483 155052 269 603 856025 168 290 376446 399 401 146497 442 517 57420 234 705 688600 277 446 908895 296 557 92911 437 728 195278 39 225 821749 628 633 591037 91 464 51109 170 505 903835 363 612 596099 287 554 928301 641 700 945875 250 359 230305 347 633 929068 436 637 571587 596 710 944074 346 379 974853 306…
Output: 1151457

Example 3:

Input: 1010 1009 1 1010 820 900 157237 279 409 68050 489 619 693428 99 560 147473 620 918 8893 620 942 859489 183 400 268947 867 942 429869 64 552 458434 173 504 262635 132 789 506926 619 655 322437 620 824 397395 399 702 650278 860 890 596922 268 458 993952 267 441 15214 403 715 140962 295 753 351919 283 590 871790 249 262 512202 528 720 999557 653 759 309949 245 828 82984 749 755 468722 20 473 588244 95 722 313235 783 892 843201 694 847 212986 74 632 293659 171 262 478428 471 823 220649 217 689 113982 325 928 615903 19 960 66954 531 713 46826 654 784 461111 588 968 328033 549 903 339912 641 738 140654 732 877 532476 462 520 487608 482 628 980530 633 754 644825 155 840 704467 937 965 251643 342 686 409733 46 544 932320 291 1000 838389 362 766 754941 286 909 882366 774 796 489323 333 678 271263 2…
Output: 2356561

Constraints:

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

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