CT53823

Sahil Counts the tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the ivory gates of Alabast, Sahil the clerk keeps careful count of the tunnels. Document the rare sighting, every figure matters. 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 <= 1411; 0 <= m <= 4233; 1 <= s,t,u,v <= n; 0 <= w <= 1000000; distance fits 64-bit.

Example 1:

Input: 952 951 1 952 44 725 408589 63 345 752974 237 392 55652 101 905 824886 159 529 735800 82 859 619754 246 443 936586 117 372 378567 19 868 863926 382 744 177924 147 257 492592 441 543 373727 457 783 759318 335 742 274114 45 341 690034 398 473 325345 29 912 407161 547 781 666637 669 742 798909 626 663 433962 230 277 863928 588 922 355653 477 503 101789 195 276 579683 329 373 844151 484 717 593275 244 617 477080 77 340 917983 77 921 396596 377 429 924755 282 300 982558 232 398 514872 289 908 56693 274 679 664315 502 615 814779 55 162 744957 36 49 119862 268 932 264588 754 884 881664 229 723 976949 702 948 389580 453 501 424104 255 880 832615 317 493 74350 628 690 910411 171 412 200029 109 266 911829 522 779 365736 483 683 25394 49 614 968526 454 818 835983 466 735 999291 305 919 892352 596 625…
Output: 3799924

Example 2:

Input: 759 2917 1 759 317 389 410787 195 695 690919 368 492 483264 196 495 969705 510 611 541276 117 361 705519 287 408 13622 243 642 714825 6 666 305030 221 436 556096 442 497 778872 495 516 687955 30 457 234263 63 180 322564 588 727 381565 627 650 309798 256 636 248711 341 607 761927 158 732 241937 127 172 84090 217 447 962419 116 634 383637 75 380 218604 100 549 944822 85 132 866913 161 442 217808 331 407 495401 309 314 209738 279 712 638574 126 164 500101 334 346 257543 66 242 584758 94 505 101103 174 539 619775 409 615 903288 325 410 126829 411 552 357570 396 647 261109 279 476 133275 537 623 29796 150 199 790129 5 400 198302 175 334 237201 32 141 208116 517 539 851963 170 694 370077 179 601 395185 574 638 560561 230 308 298485 138 658 223258 581 640 648030 505 737 986422 422 675 167908 223 …
Output: 1121810

Example 3:

Input: 913 3742 1 913 308 889 885014 616 772 883558 474 890 133964 237 403 407347 246 819 768163 25 384 565757 178 727 728776 86 215 618065 45 615 384455 146 171 454710 252 763 680032 807 835 451668 29 760 919166 2 874 707538 322 723 377898 528 639 953159 510 582 513029 86 755 378403 240 554 604358 445 468 523509 839 859 864524 283 576 513037 146 183 792946 405 611 511347 49 55 897244 204 361 704614 774 845 215172 371 676 677615 706 716 677930 744 752 361649 384 712 176785 197 259 812896 105 788 848320 425 545 738846 334 372 329152 216 611 517318 184 422 912481 379 587 300238 763 897 516462 160 485 466991 211 888 746563 711 717 430004 572 859 80353 157 418 686892 248 839 582647 140 592 612390 406 783 487864 69 114 339311 198 602 366041 321 602 161327 703 711 341351 241 791 266073 474 699 244463 5…
Output: 1028603

Constraints:

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

Loading...
Test Cases:No test cases
No test cases available.
Sahil Counts the tunnels - MEDIUM Coding Problem | CodeTikki