CT53635

Xara's Fewest Hops Ledger

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Xara inherited the ferry office at the old quarter of Brasshaven along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 2917; 0 <= m <= 5834.

Example 1:

Input: 1220 5000 1 1220 511 765 689 983 447 788 456 920 174 1001 23 1031 354 1196 461 551 254 869 350 415 703 1077 124 949 421 920 44 124 436 980 712 1189 232 1023 1121 1185 293 580 47 1178 376 520 393 546 696 741 590 966 51 374 359 1032 772 1008 84 251 409 415 863 1113 329 429 853 1042 706 1046 4 105 494 848 763 1113 841 1191 131 820 541 780 602 715 61 483 443 1215 136 280 563 722 32 100 296 936 180 867 315 811 491 733 445 608 33 1195 844 1051 558 902 734 926 232 1117 129 462 437 1171 105 858 575 637 881 1057 644 1210 260 336 188 625 724 1216 764 1086 420 857 480 1208 601 682 186 510 787 1157 1000 1055 362 1023 859 958 384 641 426 898 20 531 575 995 546 1022 207 1010 623 624 546 809 388 472 473 688 1022 1198 93 601 598 714 1075 1080 432 477 693 817 521 1107 197 837 889 1175 73 223 162 223 186 36…
Output: 4

Example 2:

Input: 2217 3031 1 2217 879 1185 700 1684 486 1735 1437 1690 994 1733 40 844 1359 1820 290 713 1436 1502 1309 2137 1760 2113 1304 1503 1120 1570 403 810 751 893 1209 1986 5 1850 371 406 211 2042 776 1477 133 2043 215 485 384 418 1772 1886 355 1716 37 2162 119 1885 348 1557 1931 2190 585 1663 793 2082 1801 1822 2049 2101 438 1200 72 637 933 1358 224 780 52 1866 558 957 1553 1653 1649 1947 984 1083 678 1481 863 894 916 1350 827 1580 599 630 657 816 938 2217 361 414 344 1384 1734 2147 805 2002 690 1235 825 1906 49 1499 113 703 281 1723 361 488 461 1660 210 2204 195 1084 342 2142 687 1884 1357 1644 764 781 1099 1445 590 1421 33 1867 248 1837 1861 1869 1282 1378 990 1472 1989 2090 1426 2080 784 1202 162 712 240 2009 1697 1842 58 1443 972 1993 1093 1256 1408 1695 1952 2045 621 1472 217 1445 184 1732 12…
Output: 6

Example 3:

Input: 2445 2826 1 2445 429 895 2246 2404 119 132 1439 2126 814 2426 488 564 885 1307 975 2303 510 849 368 1985 444 1600 1191 1725 212 2208 1182 1381 152 1176 1143 1954 1441 1756 613 1261 956 2037 1632 1809 134 1761 959 1582 816 2210 555 839 166 2098 420 2073 473 1424 1908 2098 1837 1978 523 1438 2065 2386 669 1014 1634 1933 714 988 75 1165 253 1044 1546 2337 1171 2092 138 1774 65 1070 1127 2270 1456 1899 1169 2006 655 1311 779 1563 305 1809 2192 2400 1494 2043 2182 2316 646 936 1272 1283 2249 2432 1176 1942 216 1733 1568 1919 161 1879 1107 2273 718 1895 964 2059 113 902 745 1067 2064 2410 1299 2384 1386 2039 668 2338 1387 2092 594 792 340 1957 490 2138 91 638 744 1113 2008 2212 405 447 352 1217 1221 1502 189 1681 414 2095 734 1092 847 1942 876 1953 1490 1635 577 901 307 2259 363 1409 1566 2393 1…
Output: 12

Constraints:

1 <= n <= 2917; 0 <= m <= 5834.

Loading...
Test Cases:No test cases
No test cases available.
Xara's Fewest Hops Ledger - MEDIUM Coding Problem | CodeTikki