CT36165

The Fewest Hops at Stormrest

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Caravans arrive at the cliffside roost of Stormrest with crates of routes, and Tarun the surveyor must account for every last one. 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 <= 1789; 0 <= m <= 3578.

Example 1:

Input: 1725 2031 1 1725 1615 1637 1328 1579 1538 1565 232 1299 1049 1253 328 380 1001 1516 1031 1564 244 1566 23 1282 569 1073 299 845 809 1545 987 1541 85 175 641 1454 352 1351 136 1324 989 1576 305 1721 241 819 660 1076 650 1670 503 762 392 1531 878 990 1605 1701 163 1259 383 1678 346 764 1333 1554 967 1185 1261 1585 997 1035 286 772 154 548 126 416 470 873 199 1375 17 758 1109 1580 535 1715 167 383 251 863 432 1207 685 766 809 1374 873 874 75 1316 187 1659 686 1401 825 1030 185 629 929 1038 688 1276 215 1176 129 298 419 823 555 1689 1618 1666 1185 1304 534 1493 115 1376 731 1108 151 440 1439 1595 705 1627 1363 1629 171 354 391 1065 13 1444 847 1598 388 972 1576 1603 1023 1668 104 977 841 1525 824 1248 621 884 1232 1316 995 1678 1028 1494 753 1637 418 577 379 435 536 1574 200 460 659 1067 151 9…
Output: 7

Example 2:

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

Example 3:

Input: 1166 3232 1 1166 344 844 139 883 305 874 86 1065 341 944 702 1157 276 478 27 713 118 733 856 1155 124 438 35 196 495 761 87 550 6 524 358 924 203 1085 854 1118 69 1162 6 899 628 771 340 356 314 808 916 963 240 528 551 599 24 113 627 717 65 89 529 827 1049 1051 249 974 333 582 350 527 175 1107 294 603 99 309 371 789 262 959 104 1151 462 1022 298 362 312 514 500 545 344 385 84 986 822 943 171 740 21 693 330 629 461 834 739 779 335 963 269 942 713 767 645 988 723 767 660 949 799 961 776 1097 266 726 905 948 493 676 685 790 28 717 452 1104 488 896 26 1061 188 860 165 925 195 1122 874 924 253 871 394 518 34 1097 13 885 90 672 107 1067 567 671 76 553 1097 1166 606 834 873 941 182 599 370 1146 257 653 706 888 302 553 567 780 126 1041 13 116 432 719 232 687 287 950 526 625 10 531 201 345 211 780 8…
Output: 4

Constraints:

1 <= n <= 1789; 0 <= m <= 3578.

Loading...
Test Cases:No test cases
No test cases available.