CT45801

The Fewest Hops of Brimstone

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the sulphur springs of Brimstone as Koda unrolls the day's manifest of bridges. The tally will decide the next shipment. 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 <= 3277; 0 <= m <= 6554.

Example 1:

Input: 75 2775 1 75 5 37 8 24 18 56 14 26 6 45 6 58 20 32 19 70 28 44 4 52 67 71 23 24 3 23 9 58 2 18 10 25 22 23 28 56 27 32 16 24 3 59 49 73 45 50 40 43 27 50 50 54 3 70 18 40 51 56 53 58 12 59 19 36 36 63 23 74 47 60 2 66 35 74 68 73 6 37 9 18 57 70 2 20 15 38 31 72 12 36 44 51 71 75 53 70 26 52 29 50 18 23 54 56 20 48 8 69 8 21 32 48 12 14 57 74 18 62 13 35 25 51 26 41 35 61 13 45 19 26 44 67 10 55 37 72 70 73 37 66 49 70 18 66 29 47 11 65 42 55 18 45 5 43 9 44 42 64 13 43 26 35 22 35 31 44 37 59 12 72 8 48 33 50 6 65 49 66 7 12 17 20 1 35 34 48 23 52 57 64 27 33 70 71 37 41 12 29 1 51 15 31 11 51 7 13 8 9 22 68 13 44 21 33 16 73 7 19 54 57 2 40 71 72 17 30 4 63 8 53 10 68 35 60 12 66 17 41 19 37 14 31 68 72 39 57 11 24 30 64 40 52 14 18 16 64 3 67 51 58 45 66 49 72 34 64 25 72 27 73 22 62 23…
Output: 1

Example 2:

Input: 3115 3114 1 3115 805 3030 2206 2866 933 2592 1594 2107 270 1586 801 1263 1338 1981 269 2638 376 570 2139 2548 1670 2002 213 1971 754 2205 507 1519 856 1693 686 1119 510 1413 1828 2255 409 1380 2435 2794 313 1775 563 1936 1646 1804 1627 2584 1467 2839 517 1138 2156 2710 1642 2501 2641 2801 845 1038 1878 1944 1138 2612 1071 1103 1120 2466 1312 1473 61 569 562 840 1321 2093 794 1650 2151 2753 1174 2795 1296 2865 2195 2875 116 1303 1223 1650 1074 2306 1 1484 1164 2428 711 2147 228 1481 1660 2988 538 1964 1457 2870 1093 2271 2921 3021 1992 2075 723 1755 572 1862 45 1781 593 3026 1651 1682 996 1288 263 2587 1112 1435 179 1436 276 3027 592 670 460 2123 1062 1713 468 2153 1480 2046 1364 2647 1782 1822 2055 2929 143 2968 560 3031 572 1623 91 371 1203 1578 950 3032 250 2747 726 1559 374 2736 935 194…
Output: 10

Example 3:

Input: 2431 2430 1 2431 1364 1892 630 808 410 1700 623 2073 1890 1980 717 2149 742 1073 101 1914 1672 2427 305 956 944 1814 1584 1963 831 1226 1160 1709 434 1839 566 1321 2168 2188 1285 2267 496 688 166 1396 558 598 512 1963 502 777 1217 1803 42 951 766 2050 1598 2261 1414 2030 175 930 618 761 338 1709 719 1489 550 1159 549 2314 459 2260 219 2023 465 1479 884 1054 1285 1936 1345 1370 359 2251 514 2336 387 1888 216 2179 702 1054 1078 1201 207 2146 1343 2060 1155 2227 1854 2379 251 631 893 2371 23 39 1797 2185 527 1685 221 2086 511 1918 79 1417 1623 1651 2314 2333 32 631 1008 1366 427 1073 798 1621 713 2158 1359 1483 1506 2209 8 757 91 942 1984 2094 63 2332 1633 1989 1082 2044 1227 2412 1222 2194 214 2381 82 730 171 2412 808 2305 1655 2341 10 2143 840 1933 623 2072 648 2257 315 453 456 1133 1082 11…
Output: 7

Constraints:

1 <= n <= 3277; 0 <= m <= 6554.

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