CT35303

The Fewest Hops of the Verdant bridges

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the port of Emberfall; Archivist weighs the day's bridges manifests and starts the calculations. 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 <= 3618; 0 <= m <= 7236.

Example 1:

Input: 2416 2415 1 2416 1454 2416 1556 2092 282 1867 105 972 1688 2128 2021 2176 1645 2109 1651 1797 1149 2186 812 2335 1125 2144 195 2069 345 2119 1538 1917 34 2286 1552 1623 249 698 108 1842 1208 1397 721 1036 12 606 1443 1895 206 2028 1370 1467 1452 1839 734 2322 1083 1962 52 1017 648 1949 88 2277 802 1119 1571 2385 684 1128 1040 1076 1038 1317 141 586 46 2118 1012 1665 270 2388 1393 2351 925 1002 51 1730 296 1547 45 2221 270 2176 113 633 405 2208 1156 1890 69 892 1067 2354 1864 2095 27 741 1189 1729 648 1631 1495 1780 501 1640 947 2412 263 1863 557 1122 1771 2213 483 2202 1089 2216 338 863 164 504 1550 1884 786 2258 1974 2342 89 2010 341 987 402 1780 1464 1948 268 800 1364 2265 1712 2108 1815 1911 623 1463 382 1249 1600 1844 246 1887 296 990 1257 1907 117 1343 471 1876 70 275 33 557 776 1720 …
Output: 19

Example 2:

Input: 2571 2570 1 2571 1006 1311 167 1852 106 1241 1438 1976 1481 2015 1166 2556 930 2442 796 2036 1116 2278 1439 1681 1864 2117 1051 1662 884 2257 213 1404 1703 2103 628 2355 880 2440 216 988 371 635 729 2556 961 2248 37 410 721 1052 547 976 922 2503 242 481 1105 1905 183 2441 2120 2432 63 502 1477 1828 358 1288 585 2162 744 814 1672 2230 2014 2248 1152 1806 113 240 1094 1999 200 1262 1853 2420 104 2082 458 1603 684 917 267 1952 1069 2456 179 1864 395 1223 1201 2383 1944 2099 228 456 414 2508 1486 2017 277 1045 892 1615 197 1670 226 2067 193 324 294 697 426 2501 76 1536 167 838 415 1044 136 1793 667 2034 199 1549 1180 1413 1382 2183 1206 1837 525 1407 1164 2085 824 1004 1763 2028 476 1586 221 368 90 1199 999 1796 451 1703 1272 1891 414 1104 575 2068 227 1375 1519 1946 281 1669 479 2197 57 1686 …
Output: 12

Example 3:

Input: 2688 5106 1 2688 2011 2476 2000 2153 336 1928 1882 2506 406 835 771 1065 410 1706 387 1683 116 905 1315 1627 1466 1468 31 2376 665 1839 689 963 2446 2600 515 693 714 1340 1749 1898 1332 2233 791 1614 874 1376 797 1225 607 890 142 205 34 81 776 2518 130 2005 457 2544 1881 2262 487 1061 1048 1502 1199 2223 1160 1745 942 2057 224 2656 1719 2231 13 27 60 1978 1909 2229 256 1739 489 1740 1965 2168 287 1095 1326 1655 132 577 1197 1947 1448 2026 1586 2040 396 811 595 2566 1906 2497 668 1242 367 2645 1136 2438 868 1275 598 779 1333 1801 369 981 1589 2150 973 2475 1273 1328 30 1824 735 1712 545 783 668 1314 330 2160 1774 2105 157 2507 972 2360 817 911 1809 1810 390 1888 333 1409 1153 2424 324 598 825 2553 930 1755 592 1263 363 2677 135 2479 560 1214 768 888 63 1129 1020 1589 1761 1892 2073 2247 187…
Output: 6

Constraints:

1 <= n <= 3618; 0 <= m <= 7236.

Loading...
Test Cases:No test cases
No test cases available.
The Fewest Hops of the Verdant bridges - MEDIUM Coding Problem | CodeTikki