CT39902

The routes Fewest Hops Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the cedar groves of Balmcrest close for winter, Rowena must finish the routes ledger - one figure at a time. 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 <= 2436; 0 <= m <= 4872.

Example 1:

Input: 1980 4193 1 1980 709 1766 962 1666 1351 1615 166 404 103 1913 176 1404 336 1157 1413 1940 962 1091 737 1667 413 1503 531 1045 95 117 173 1309 222 893 146 378 1187 1491 28 1112 381 1928 577 1575 445 461 1215 1635 1373 1703 605 946 962 1344 167 1623 1596 1610 484 1692 136 1463 1535 1594 375 875 95 1508 77 423 409 668 404 827 307 857 592 1702 578 1932 125 742 112 1676 86 1967 836 1523 415 760 386 1522 188 1620 744 1903 347 396 616 1590 450 794 1584 1924 780 1586 302 1660 396 1727 1346 1494 185 668 1117 1455 17 20 1241 1293 1474 1676 304 1034 376 1149 662 1546 213 1438 1696 1717 930 1228 555 1417 154 739 567 736 303 1118 817 930 1227 1399 1359 1557 768 800 1461 1747 733 1894 416 923 396 517 26 913 30 1571 403 934 969 1612 942 1195 207 1739 89 1341 34 1400 1204 1762 386 1742 927 1966 974 1571 2…
Output: 5

Example 2:

Input: 1302 2075 1 1302 134 1175 38 117 39 842 620 1198 30 557 499 558 350 1146 1141 1294 221 807 984 1230 687 840 734 795 92 107 5 767 197 895 821 1076 223 444 699 808 549 988 259 640 707 743 633 855 286 1281 568 1111 10 931 145 1187 3 566 231 867 492 1298 840 863 117 1007 239 842 1 910 636 1070 1118 1146 17 1013 42 689 908 941 846 1070 774 787 59 362 622 648 468 590 344 1191 216 652 77 638 6 801 548 839 60 1257 491 572 752 887 182 1002 607 1292 426 677 718 900 237 978 141 343 257 1276 869 1026 63 940 4 1296 785 1209 310 490 1067 1116 235 419 43 549 473 913 50 937 430 1139 538 912 634 1122 313 746 155 208 416 1253 356 1276 853 1064 878 958 160 293 176 978 182 1024 220 285 824 900 648 1295 774 1190 710 1102 64 1299 67 206 193 253 515 1099 1104 1122 77 250 143 832 650 1245 74 266 532 581 371 1241 …
Output: 5

Example 3:

Input: 2112 4327 1 2112 166 1982 907 1721 19 1244 373 1254 963 2035 561 1773 455 1176 1541 1706 274 1670 889 1170 2059 2106 82 563 1442 2103 995 1639 1158 1273 385 1542 1225 1655 1403 1655 724 1104 514 975 1719 2107 115 237 486 1625 848 1283 1233 1933 283 1436 66 781 715 2091 1533 1936 34 113 658 1189 1452 2004 816 1901 1213 1313 1448 1665 404 1697 712 1325 1287 1893 244 2004 1094 2080 405 1211 1693 2045 407 1927 867 1062 193 2064 838 865 1068 1586 398 849 891 991 899 1124 221 1154 1085 1421 1951 2096 145 1213 565 744 236 848 1440 1615 13 1491 248 312 68 88 1274 1325 567 857 696 769 18 912 1144 1376 709 1403 566 1901 243 1972 1198 1683 267 576 629 1173 185 957 954 1377 562 1201 1486 2071 1030 2083 519 1652 593 1365 619 1990 499 1076 421 1678 512 771 1761 2085 342 1966 82 1570 1074 1196 807 1735 5…
Output: 4

Constraints:

1 <= n <= 2436; 0 <= m <= 4872.

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