CT42237

The Fewest Hops Beneath Leatherwick

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the tannery row of Leatherwick opens only for a perfect tally of canals. Ranger means to find out. 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 <= 3048; 0 <= m <= 6096.

Example 1:

Input: 1263 2330 1 1263 497 991 289 1204 488 728 367 1032 518 649 91 837 211 509 799 844 122 703 643 1160 207 592 386 1241 677 1070 353 1108 396 1158 424 573 1031 1037 208 474 545 872 206 1150 35 837 137 410 36 722 415 525 940 1118 1028 1031 377 840 34 840 30 538 596 1039 89 545 620 855 754 887 329 820 529 764 564 805 719 1001 294 906 675 699 1066 1254 397 622 103 854 300 873 986 1098 246 800 526 1182 26 179 178 814 518 527 288 323 989 998 171 1081 958 1018 61 93 90 338 348 695 74 1217 1052 1147 709 1006 382 842 249 283 555 701 47 282 515 717 924 1168 464 893 360 837 886 1025 760 1020 10 52 208 1072 159 865 624 998 47 495 739 1117 374 435 188 1095 184 1045 30 989 831 1137 436 953 32 693 416 1212 843 1162 167 762 191 349 78 532 175 646 529 1230 232 323 823 825 201 413 109 1250 366 1159 401 737 425…
Output: 5

Example 2:

Input: 2761 4537 1 2761 79 2145 1606 1983 158 1295 1389 2555 1541 1800 2205 2432 686 1907 91 96 509 1172 126 2737 1002 2358 436 2389 597 2404 1557 2380 7 1523 216 2479 497 1835 2103 2622 1582 1864 530 2011 614 674 83 704 97 2286 52 1530 1452 2522 2043 2355 2306 2478 2108 2474 1343 2484 454 1201 1298 2170 14 680 1086 1259 1057 1151 818 2081 1399 1928 1153 2223 670 1893 1193 1794 1569 2278 1082 2622 1097 1463 128 1040 1877 2065 2337 2440 2 1201 149 1673 1606 2355 494 700 64 394 557 762 1262 2650 1542 2228 17 1161 598 624 769 2454 1252 1306 12 114 1836 1909 355 2306 2036 2463 178 2251 1544 1756 2200 2616 693 2099 540 2142 1280 2592 2528 2706 1744 2404 1053 1664 1794 2104 778 2101 1377 2495 2228 2722 488 2015 553 859 3 1357 1356 1988 1395 2277 1290 2227 1400 2286 749 1789 951 2683 1569 2313 1702 2024…
Output: 9

Example 3:

Input: 2814 5874 1 2814 1224 1906 950 2114 691 1030 701 2290 272 2139 170 2220 1810 2626 1790 2292 1383 1804 40 2107 474 2495 1267 2734 2181 2704 914 2707 677 2271 149 2136 1801 2660 1719 2304 405 2468 2281 2518 1377 2720 2014 2435 719 2224 720 1958 2415 2577 1060 1506 958 1468 319 984 434 787 1518 2208 250 1858 810 2521 647 1732 972 2180 1200 1259 372 1304 676 886 1941 2687 1669 2810 1093 1556 1128 2674 970 2079 273 2156 1676 1759 351 2478 222 869 1060 2487 390 1979 2147 2164 2018 2242 1131 2506 430 1672 1542 1779 550 1746 746 2021 2590 2655 1555 1633 584 1100 32 90 228 2784 125 2445 2139 2384 1852 2647 1256 1301 1870 2722 437 1579 1277 2472 232 657 1289 2319 238 2271 1743 2499 133 1383 1589 2590 1437 1609 1933 2035 1353 1577 204 295 1034 1909 1573 2444 686 995 780 1379 400 1419 553 2260 562 264…
Output: 4

Constraints:

1 <= n <= 3048; 0 <= m <= 6096.

Loading...
Test Cases:No test cases
No test cases available.
The Fewest Hops Beneath Leatherwick - MEDIUM Coding Problem | CodeTikki