CT45479

The Fewest Hops of Vermilion

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

It is audit day at the cinnabar mines of Vermilion. Navigator spreads the corridors records across the table and picks up a sharp pencil. 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 <= 1751; 0 <= m <= 3502.

Example 1:

Input: 1087 1086 1 1087 71 511 666 880 677 756 105 168 871 887 276 352 138 161 324 835 85 108 260 588 687 762 89 221 99 180 122 212 211 677 601 979 56 150 478 491 630 932 670 1015 546 877 652 760 769 942 451 802 226 602 899 1038 147 885 423 634 51 565 335 702 360 419 65 826 7 180 83 300 308 743 382 604 579 1055 88 334 121 837 130 391 55 537 448 914 188 641 695 990 134 171 167 741 83 293 144 221 57 110 146 395 47 928 9 129 78 327 255 866 488 684 223 272 477 1087 738 973 517 927 393 912 583 839 674 715 43 697 342 1032 289 521 874 965 123 232 301 393 678 861 258 951 526 797 207 931 698 806 460 541 206 872 258 775 902 1016 368 530 276 477 504 750 75 1057 692 900 388 1059 88 658 200 586 337 391 62 787 909 923 436 654 635 895 571 993 40 520 928 1018 404 406 114 434 102 113 257 680 208 455 704 911 48 84…
Output: 10

Example 2:

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

Example 3:

Input: 904 903 1 904 267 294 134 393 357 522 86 668 91 460 232 846 292 469 417 634 195 773 109 652 299 814 148 503 186 284 101 439 424 684 240 635 65 390 271 464 88 589 505 778 245 351 131 460 259 290 599 762 156 171 436 665 120 497 12 879 7 500 204 560 121 506 10 647 116 446 298 401 124 200 187 588 21 711 779 791 148 342 294 627 450 503 704 803 67 751 552 604 345 396 179 718 422 868 155 804 439 589 341 760 308 890 75 763 240 702 89 459 494 833 136 483 594 853 224 681 303 568 67 499 32 304 108 876 71 97 560 677 154 591 38 661 214 657 327 835 50 730 252 322 150 376 423 536 182 287 205 483 455 504 787 850 97 843 211 527 551 634 26 142 162 415 399 767 156 439 232 655 143 259 134 707 215 310 589 853 32 548 11 834 163 737 192 631 307 548 620 904 633 850 551 636 422 870 435 494 618 689 108 600 402 532 …
Output: 10

Constraints:

1 <= n <= 1751; 0 <= m <= 3502.

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