CT40650

Northern tunnels Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the temple city of Sunspire; Ivan weighs the day's tunnels 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 <= 2966; 0 <= m <= 5932.

Example 1:

Input: 2813 4283 1 2813 913 1800 454 1246 2027 2418 1699 1702 239 1712 1103 1906 506 2315 335 2148 454 1166 858 1421 642 1645 997 1431 1292 2706 948 2291 755 1836 908 1811 699 1189 2314 2416 438 1361 557 694 1249 1931 249 887 936 1733 1394 2270 547 1091 1744 2269 919 1381 688 908 1820 2750 249 1927 1525 2482 36 1231 1710 2545 413 1378 205 743 1327 2464 142 2702 65 960 2298 2557 1646 2221 1056 1827 1018 2719 587 1611 389 2061 42 2278 2449 2663 1133 2599 2130 2684 2287 2295 2218 2466 718 1233 750 1877 399 564 205 1145 498 1624 2328 2376 828 2508 516 599 2164 2199 150 159 192 1607 1738 2068 386 2770 244 2122 1384 1673 138 2586 466 2259 95 2775 1082 1681 1140 2737 2143 2256 716 2502 617 1244 66 2097 480 806 1888 2806 1252 1591 1824 2116 828 2321 1077 1106 520 2462 2043 2217 588 2221 67 2060 1073 2240…
Output: 7

Example 2:

Input: 2864 2863 1 2864 1252 2541 1312 2834 775 2227 545 2391 2000 2374 1437 2626 57 951 319 2563 1475 2557 848 1891 643 2096 1497 1776 139 488 1841 2608 24 138 1339 1586 10 2643 435 477 579 2864 822 2422 1481 2529 1843 2845 1433 2290 356 1802 1617 2436 198 1127 1512 1629 489 1192 1047 1642 712 2854 1221 2398 648 1527 465 2067 564 2018 2469 2705 2259 2770 972 2860 1403 2604 1115 1755 412 728 575 1958 41 1395 875 2703 1164 1277 503 674 246 2398 1797 2106 1558 1814 1072 1154 1770 2126 95 2595 436 1522 493 2060 156 2640 561 1272 2076 2622 581 890 798 1980 473 1455 1257 1859 254 1780 249 2671 96 1252 230 466 1778 2413 1367 1679 1097 1639 970 1993 174 2613 840 2299 1902 1975 1405 1776 2152 2724 1549 2681 305 850 1273 2145 1719 2348 211 1634 1308 1549 469 2118 86 2536 316 1932 680 1507 676 1843 644 127…
Output: 15

Example 3:

Input: 2777 2776 1 2777 2077 2500 292 2324 282 1903 230 1629 43 711 196 353 575 1096 36 1913 1227 1920 172 761 1687 2680 811 1529 1987 2337 537 1167 799 1223 1132 1575 11 1946 875 903 988 1622 905 1821 2024 2150 206 840 488 1923 1182 1822 104 2500 278 1285 1424 2386 599 875 357 1754 1311 2679 1000 1507 981 1966 1132 1883 684 1805 968 1315 199 898 168 2009 857 884 1666 1737 1166 2215 1983 2635 630 2718 1757 1779 92 781 1308 2721 565 2202 779 1795 717 1231 1819 2752 1229 2120 1075 1928 265 1912 1274 2220 785 2468 813 2369 2001 2642 504 2377 43 1434 2272 2537 523 1362 1404 2588 701 2065 747 1547 96 472 390 556 1177 2342 902 975 1611 1671 1695 2523 2050 2625 83 784 2326 2346 854 1300 459 798 1019 2723 2533 2714 339 1468 1873 2542 19 2450 557 1881 1725 1803 2102 2248 1547 1853 277 1914 1834 2388 2197 …
Output: 13

Constraints:

1 <= n <= 2966; 0 <= m <= 5932.

Loading...
Test Cases:No test cases
No test cases available.
Northern tunnels Fewest Hops - MEDIUM Coding Problem | CodeTikki