CT45427

Devi and the Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Devi inherited the bakery at the herring shoals of Silverfin along with its curious bookkeeping system for routes. Time to make sense of it. 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 <= 2149; 0 <= m <= 4298.

Example 1:

Input: 974 2162 1 974 512 812 58 701 11 225 57 600 443 849 114 408 152 959 301 463 137 372 676 855 22 602 150 682 537 649 39 541 34 571 485 807 195 565 122 393 68 247 504 963 890 974 282 466 178 316 725 804 277 418 842 953 79 481 108 752 385 420 231 549 53 209 363 417 58 601 695 938 77 337 440 935 383 693 470 853 166 829 158 580 19 620 344 733 318 481 595 737 602 931 485 493 119 158 365 457 330 455 818 842 7 480 521 925 11 554 807 864 32 422 56 453 473 756 181 740 553 952 404 965 184 425 38 303 416 462 182 929 609 957 530 949 10 222 64 393 276 682 689 752 680 864 61 490 274 463 346 730 69 588 227 502 782 789 265 828 423 488 96 489 466 505 277 444 509 735 132 227 684 712 148 359 405 575 417 671 876 912 420 675 226 829 64 754 25 57 536 744 202 586 579 597 687 700 261 659 195 844 759 910 360 832 674…
Output: 5

Example 2:

Input: 2080 2699 1 2080 1501 1909 751 1149 704 1966 1442 1610 40 1233 568 1513 95 1409 480 804 431 1769 340 1004 372 418 222 1242 324 371 1274 1667 47 1705 386 710 1058 1417 712 2015 1438 1483 1789 1858 177 414 1109 1247 133 1672 456 1828 609 2068 408 1919 941 2056 718 870 234 1070 1372 1779 358 1684 530 1591 127 1982 124 939 418 444 289 738 450 1192 480 1363 75 2063 929 1816 517 1171 896 1936 284 863 1670 1850 541 1777 22 353 700 899 673 1865 346 1305 1748 1986 668 704 936 1810 259 809 1723 1732 142 1594 538 656 1186 1297 55 301 160 1524 1311 2073 640 1839 904 1623 7 1299 1102 1267 65 701 1761 1884 1195 2005 1663 1939 1542 1785 68 1773 894 1833 5 726 180 1713 539 1703 172 1508 1004 1180 530 1063 752 1891 1235 1483 66 363 1 1554 454 663 650 995 189 1334 50 1362 788 1273 12 1264 534 1140 126 1349 …
Output: 8

Example 3:

Input: 1712 3532 1 1712 770 859 413 1017 45 1326 816 1362 726 982 819 1396 570 1494 922 1135 932 1563 578 1118 1035 1366 4 557 739 1268 284 1300 889 898 470 933 506 568 215 1134 129 1158 435 1442 538 794 866 1388 877 1607 1286 1407 866 1344 440 1566 163 1160 844 1576 79 814 139 1183 219 1102 1302 1627 908 1322 309 874 988 1265 1242 1282 970 1104 77 969 143 195 540 918 976 989 6 1323 219 1321 209 1090 62 1616 193 627 888 1700 957 1365 33 871 316 1018 217 741 366 1328 588 1613 2 712 1201 1601 1429 1492 246 1374 671 1006 412 585 95 1283 929 1138 1286 1301 183 219 428 1123 294 1075 78 1602 196 1525 878 980 443 606 989 1191 1375 1526 205 920 898 1501 484 584 605 1657 709 1045 544 594 126 1351 109 160 732 1326 151 688 1099 1292 252 565 1459 1476 202 1333 112 1499 185 411 999 1015 499 912 1108 1456 474 …
Output: 6

Constraints:

1 <= n <= 2149; 0 <= m <= 4298.

Loading...
Test Cases:No test cases
No test cases available.
Devi and the Fewest Hops - MEDIUM Coding Problem | CodeTikki