CT32844

Finn's Fewest Hops Ledger

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Finn found an old ledger of tunnels in the kitchen attic at the railway depot of Cinderline. The margin notes pose a precise question. 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 <= 1570; 0 <= m <= 3140.

Example 1:

Input: 1419 2214 1 1419 352 704 146 1249 238 1198 973 1335 648 1403 254 1186 614 856 1142 1248 159 798 459 924 201 1369 348 1001 228 883 779 1260 204 562 723 1160 1054 1419 969 1402 176 1121 181 1199 881 1184 560 1012 201 830 1265 1284 1015 1403 246 948 822 1252 1326 1354 125 362 805 1204 523 1337 909 1183 485 624 425 999 353 490 511 1226 728 865 259 997 709 868 601 999 198 361 1013 1163 1070 1187 328 708 826 1348 88 1169 975 1045 543 587 1062 1131 391 860 254 1109 23 1199 143 474 486 1376 172 254 200 929 1083 1086 144 280 900 1241 225 1208 752 798 215 432 2 410 481 741 846 1199 164 929 998 1138 563 1386 401 421 253 915 86 924 479 846 952 1177 21 243 6 682 224 865 856 990 795 919 260 910 269 620 721 831 407 1383 194 887 101 908 534 758 404 891 455 651 182 938 965 1394 243 294 121 1055 500 809 255…
Output: 7

Example 2:

Input: 1092 2529 1 1092 289 1016 397 740 219 336 802 1016 330 489 257 946 783 972 177 339 76 130 626 1022 403 498 712 984 492 811 259 301 133 842 479 869 833 1050 313 351 261 721 868 1092 370 737 467 571 88 333 384 639 29 244 664 985 665 796 721 1016 591 1080 286 385 486 497 510 858 682 847 5 355 9 904 635 1023 566 924 159 196 18 1087 29 974 6 923 416 588 846 972 162 239 73 924 699 747 323 727 102 937 38 662 745 860 247 1043 328 1064 997 1013 635 860 102 633 579 952 15 433 69 1024 414 959 197 941 329 768 17 986 119 803 618 1080 72 110 315 978 52 900 50 634 375 662 210 635 195 894 9 224 313 656 460 516 159 235 563 648 267 669 706 1056 118 746 788 836 292 369 490 929 816 890 557 727 333 569 71 704 213 745 937 959 118 325 124 963 639 1078 172 687 96 435 311 1088 369 933 844 846 68 515 20 268 177 992…
Output: 4

Example 3:

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

Constraints:

1 <= n <= 1570; 0 <= m <= 3140.

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