CT35491

The Fewest Hops at Scriptoria

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Steward found an old ledger of roads in the mint attic at the ink district of Scriptoria. The margin notes pose a precise question. Task: Print the minimum number of edges on a path from s to t, or -1. Input format: First line: n m s t. Next m lines: u v. Output format: Print the BFS distance or -1. Constraints: 1 <= n <= 1224; 0 <= m <= 2448.

Example 1:

Input: 973 1754 1 973 617 688 121 950 188 400 341 554 70 902 136 457 273 500 726 759 52 935 2 432 8 466 43 794 447 544 907 923 47 260 144 643 94 233 670 850 2 353 259 569 403 682 470 567 536 918 432 626 198 229 645 791 17 106 881 898 646 955 291 634 67 906 309 700 116 431 70 735 562 677 414 595 17 894 131 200 840 864 528 950 335 670 534 781 283 971 329 821 320 429 54 71 724 920 326 409 79 936 514 811 109 224 36 425 176 612 157 231 262 911 831 873 198 679 70 956 164 249 62 532 666 713 584 762 320 381 713 844 400 431 437 599 106 699 550 681 440 875 119 625 558 581 397 944 489 607 425 515 221 452 184 902 23 577 26 875 636 738 216 285 194 808 578 797 852 934 193 633 270 652 275 353 291 787 464 818 665 763 104 435 71 629 17 710 376 518 185 306 171 657 475 945 167 914 163 720 150 380 242 774 148 678 22…
Output: 6

Example 2:

Input: 914 1435 1 914 32 93 51 199 182 884 337 720 198 842 281 660 153 761 103 343 199 438 472 858 15 755 433 571 375 409 405 754 152 215 428 627 382 525 393 775 235 788 69 836 114 722 698 702 139 298 204 461 295 733 277 623 152 781 624 674 335 480 34 402 92 904 47 830 490 688 186 846 212 462 195 482 482 650 459 651 345 770 335 810 382 556 135 801 407 873 243 618 479 574 699 869 655 864 766 876 26 261 181 351 295 767 268 506 398 540 627 824 777 875 14 753 66 185 364 897 515 561 3 437 498 565 298 703 402 522 33 732 240 401 187 429 302 548 537 590 98 357 248 253 38 411 450 509 583 731 558 704 150 774 402 654 388 696 369 420 156 568 18 591 769 837 124 861 466 774 422 843 402 498 720 869 455 881 626 747 63 185 453 587 241 676 79 229 26 505 69 127 698 793 442 670 67 331 521 706 579 604 415 756 766 780…
Output: 7

Example 3:

Input: 1100 1099 1 1100 711 1100 678 1068 95 921 310 716 145 1058 63 265 185 602 98 531 103 299 153 686 50 680 191 789 275 460 273 1040 215 1053 168 919 249 601 93 516 320 546 105 573 239 490 412 942 338 727 112 347 78 670 47 843 53 851 469 693 766 966 772 803 664 1008 468 899 452 765 528 585 338 365 822 857 94 597 1002 1085 108 983 295 605 42 218 294 410 499 912 138 473 210 775 498 1016 804 926 866 962 164 963 794 1003 187 691 793 883 666 921 160 682 705 780 1004 1064 202 241 83 826 528 718 517 563 903 993 258 818 646 768 526 925 643 1057 132 898 911 1039 429 850 98 787 368 819 442 847 620 718 72 1016 217 902 488 548 407 581 452 662 742 912 831 929 506 839 235 785 53 460 270 587 709 1060 65 1036 579 969 587 1031 1070 1096 845 990 154 701 759 859 136 213 372 952 297 935 433 500 706 928 51 385 605…
Output: 13

Constraints:

1 <= n <= 1224; 0 <= m <= 2448.

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