CT36259

The Fewest Hops Beneath Serpentis

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The harbor bell rings at the jade shrine of Serpentis; Sona weighs the day's roads 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 <= 1914; 0 <= m <= 3828.

Example 1:

Input: 1828 1827 1 1828 109 995 516 517 754 755 515 806 61 214 110 1049 1029 1289 1021 1250 1319 1749 473 721 1051 1300 391 470 168 735 66 426 183 1156 6 399 127 636 989 1358 351 600 170 589 649 1589 79 939 1198 1634 199 956 339 1442 1402 1439 694 794 564 1120 709 1075 929 1687 169 704 80 1025 89 609 92 1155 1285 1680 169 891 223 570 1304 1517 144 1580 563 1573 302 1520 411 1595 226 1198 240 1461 394 600 164 1237 718 1032 562 1171 1128 1770 1123 1625 166 1820 439 1298 98 992 934 1226 463 542 297 1374 121 1076 255 795 53 1643 452 710 173 1740 828 1201 454 1027 185 1566 143 1205 85 1630 41 946 506 709 658 1550 796 837 184 459 1151 1176 586 1635 1093 1387 1010 1624 678 955 1456 1779 166 465 1116 1691 57 1537 252 303 775 1237 253 1259 868 1682 25 679 387 663 456 603 518 956 99 870 298 1554 1093 1543 …
Output: 5

Example 2:

Input: 124 2179 1 124 14 99 10 57 60 96 7 63 64 65 44 113 78 112 43 86 53 63 57 104 64 103 5 80 65 100 12 34 93 97 62 95 1 97 13 118 97 110 88 116 64 97 75 93 22 41 44 99 33 62 11 30 50 112 28 40 31 117 59 81 27 73 46 119 23 30 84 97 48 85 41 102 102 104 110 117 68 118 91 92 65 83 24 92 93 124 25 88 33 110 37 105 47 95 23 49 54 123 55 70 24 116 68 69 47 102 28 112 47 110 21 73 6 113 47 109 14 108 65 98 34 121 14 56 16 73 18 85 68 72 18 107 73 104 93 120 8 41 2 32 90 118 88 123 59 117 23 41 72 113 51 92 8 92 26 35 57 105 12 20 26 58 97 104 76 78 50 101 61 119 68 123 42 109 5 103 90 91 29 91 49 98 8 57 98 105 37 92 53 114 5 116 48 70 52 110 10 99 29 48 57 78 100 108 6 52 14 95 1 111 10 46 6 32 87 116 18 91 8 64 36 68 17 120 20 105 30 51 60 76 14 58 13 18 36 105 10 14 55 108 88 95 65 101 22 88 55 11…
Output: 2

Example 3:

Input: 1733 2895 1 1733 226 428 581 1431 904 1422 771 1660 1133 1581 43 1145 967 1170 1530 1628 626 793 27 1065 663 683 779 902 772 1644 539 1574 398 1030 537 615 905 1661 500 1476 393 1247 177 894 80 1564 557 1409 286 840 1237 1381 616 987 1064 1521 573 908 1196 1628 427 971 163 1256 234 446 393 490 75 632 1220 1716 1570 1589 956 1117 37 750 374 537 1168 1390 312 1100 1060 1730 1375 1552 378 853 667 888 114 630 1194 1212 214 701 9 1021 924 1509 839 1690 7 1242 754 971 187 1288 114 1575 229 629 385 421 72 360 1402 1472 275 508 877 940 130 742 93 881 97 1459 613 1363 1374 1588 119 587 1506 1581 864 1546 4 933 760 1002 1496 1536 1224 1728 288 964 126 1726 352 1287 537 1503 667 1659 412 586 618 1490 274 969 124 1351 567 1180 777 1317 1131 1408 693 876 247 909 318 1611 1073 1574 377 812 241 1072 375 …
Output: 8

Constraints:

1 <= n <= 1914; 0 <= m <= 3828.

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