CT41944

The Fewest Hops Beneath Ashfall

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morning light hits the ember dunes of Ashfall as Bhavi unrolls the day's manifest of tunnels. The tally will decide the next shipment. 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 <= 2932; 0 <= m <= 5864.

Example 1:

Input: 2699 5211 1 2699 516 1639 845 1162 70 1424 878 2067 93 1407 530 1498 321 2163 1513 1877 1658 2248 1057 2395 1439 2541 216 1642 1982 2208 23 738 871 1872 475 1953 445 854 228 831 2340 2698 1613 2035 304 1284 9 1990 1271 2001 1007 2455 1384 1410 2389 2633 192 1929 1200 1373 195 495 903 2491 2543 2684 255 2241 772 1384 1344 1945 148 2209 280 2243 2381 2544 51 1967 581 639 271 1134 958 2174 4 927 1459 1877 818 1537 316 2288 577 1979 968 2515 328 1777 1281 1464 447 1657 286 812 2152 2519 1225 1969 97 521 933 1772 124 1560 734 1674 1277 2577 413 985 701 1048 577 2199 422 2298 451 2076 1114 1997 1386 2135 1087 2411 452 2339 1636 2052 2228 2575 988 2283 1802 2639 1533 1913 967 988 1868 2664 1102 2198 845 1186 1408 2627 1148 1219 2416 2593 1650 2346 378 2692 835 2252 1566 2660 37 1085 1198 1531 153…
Output: 6

Example 2:

Input: 580 4837 1 580 283 451 7 393 53 504 235 551 217 506 293 370 163 458 4 384 215 430 25 537 84 238 225 534 230 474 166 481 197 538 283 324 263 346 153 196 250 311 28 225 130 527 326 562 114 477 336 547 357 359 1 502 15 573 132 409 137 402 446 516 21 363 114 541 15 535 8 117 355 469 162 178 24 41 155 353 366 442 70 277 232 326 95 271 149 533 222 224 84 450 97 257 258 546 34 234 38 463 64 150 33 430 341 481 440 468 40 175 65 194 84 464 448 576 376 569 366 468 138 342 297 497 34 501 148 401 80 215 263 437 527 534 286 352 55 243 211 356 96 307 239 558 482 573 343 378 236 490 361 451 245 259 86 356 240 536 201 555 181 371 281 539 87 255 22 290 11 488 90 562 137 230 116 167 13 399 94 516 86 163 124 187 367 443 60 571 270 547 282 299 19 246 65 528 293 516 137 288 7 561 158 216 535 567 300 423 76 375…
Output: 3

Example 3:

Input: 1072 1102 1 1072 601 891 298 410 519 535 124 1044 587 796 116 638 559 566 872 938 324 638 40 691 543 544 95 681 343 403 73 1028 613 968 457 679 612 914 836 1004 799 1038 497 1035 123 720 98 499 422 846 9 419 313 546 241 875 159 456 301 617 497 834 620 992 129 567 482 583 232 791 550 561 467 610 260 767 669 806 279 583 586 748 89 803 948 1018 716 959 605 1053 39 581 549 879 67 939 403 726 159 318 527 567 332 1044 441 561 787 1055 254 341 231 861 124 510 260 593 434 435 173 898 82 694 480 820 512 632 751 996 465 1025 174 706 190 735 407 743 736 849 915 1052 335 765 290 981 442 860 257 633 177 1008 206 822 929 998 247 535 905 1051 301 699 595 963 538 889 31 567 329 1058 98 337 497 975 105 723 252 850 268 664 529 1037 557 999 405 643 356 970 204 1055 314 922 54 611 179 1006 777 840 474 830 264…
Output: 8

Constraints:

1 <= n <= 2932; 0 <= m <= 5864.

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