CT54432

Marble bridges Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The accountant Admiral has been asked to optimize the storeroom layout. On the desk lies a long table of bridges readings. 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 <= 2340; 0 <= m <= 4680.

Example 1:

Input: 2035 4267 1 2035 1010 1191 998 1406 479 510 933 1085 1748 1968 36 1948 275 587 231 1863 769 1080 446 887 1078 1360 1568 2016 1038 1758 82 1408 1085 1624 1095 1720 1435 1756 50 1991 373 1568 818 1731 473 1165 703 1183 72 982 1518 1570 170 652 280 1732 1705 1816 249 1746 20 1590 213 405 1423 2004 72 287 408 1693 403 1671 1134 1434 1604 1636 795 1316 82 696 987 1926 771 949 503 686 416 1175 1580 1976 325 1463 1500 1584 73 236 218 260 704 1976 1091 1868 804 1454 635 711 769 841 135 1584 159 1834 136 747 1152 1702 94 734 45 1681 1337 1516 418 1543 1438 1531 1118 1150 487 1026 132 1877 318 818 237 494 669 900 794 1878 89 1448 865 1346 640 1917 82 545 104 359 120 792 1447 1710 148 1329 808 1363 1535 1843 464 486 335 1475 64 1886 959 1383 297 1613 892 1390 473 1243 381 590 740 1926 725 816 657 659…
Output: 6

Example 2:

Input: 2119 3758 1 2119 1675 2062 44 1182 57 954 1089 1551 809 1913 227 297 484 1232 370 1490 1802 1811 9 15 1124 1324 710 1391 424 1692 587 2114 146 631 528 1156 1509 1802 932 1521 841 916 1207 2071 901 1944 367 1518 1161 1185 553 1397 885 974 1311 2090 1791 2011 595 1396 879 1288 452 1887 1597 1794 1144 1848 1632 2082 1779 2008 576 1399 394 1467 741 1650 795 2035 141 1633 366 509 1231 2075 494 736 625 1313 1357 2024 1327 1826 792 1112 68 2062 880 1660 113 1936 1729 1889 398 502 891 1940 385 1120 544 1381 219 1777 1636 1900 1915 2099 1075 1834 411 913 1148 1308 1370 1783 408 1022 1206 1997 605 1087 150 1404 1659 2022 877 1339 206 1765 325 467 264 1759 1885 1980 1445 1899 298 1770 1472 2081 656 1492 633 1266 619 1575 6 1027 201 1249 11 1999 829 1847 35 1143 1732 1994 321 499 23 797 314 1985 234 5…
Output: 5

Example 3:

Input: 192 394 1 192 53 74 9 172 25 161 36 192 89 140 16 181 12 65 63 144 8 98 110 182 95 115 40 47 100 174 80 174 14 77 87 188 47 166 5 189 24 188 87 176 23 36 52 116 7 119 71 72 50 161 84 164 32 134 79 111 11 143 40 43 111 170 118 169 114 175 83 158 71 165 25 63 38 62 28 95 20 47 41 181 19 91 30 146 133 182 43 103 70 154 153 188 186 192 7 58 8 36 73 147 9 29 31 117 7 47 50 182 48 158 60 158 99 125 135 171 73 186 16 138 121 176 21 118 63 69 43 50 38 139 85 158 43 109 106 132 67 169 86 139 51 61 75 158 3 62 41 89 69 130 11 45 100 161 17 135 158 161 57 145 35 115 14 188 42 122 7 61 27 110 22 68 26 109 69 122 5 29 26 54 141 171 44 163 97 102 61 155 3 83 58 150 44 88 28 69 87 106 29 36 41 125 82 98 78 108 45 53 128 134 167 185 31 136 179 183 1 4 19 168 44 77 13 94 112 130 100 162 76 176 126 165 56 1…
Output: 4

Constraints:

1 <= n <= 2340; 0 <= m <= 4680.

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