CT50144

Morgana Counts the tunnels

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Morgana runs the dairy at the ember dunes of Ashfall. Today the books show a list of tunnels, and the numbers must be worked out before sundown. 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 <= 1483; 0 <= m <= 2966.

Example 1:

Input: 302 2149 1 302 131 230 89 206 148 229 59 136 5 140 63 257 13 24 236 272 74 208 4 38 87 99 13 298 13 118 41 176 111 175 259 286 197 202 53 264 100 135 35 57 129 130 32 171 105 117 33 184 27 172 107 268 77 206 149 163 120 272 191 242 157 297 205 259 2 12 55 103 16 294 40 297 101 222 59 160 89 232 8 46 253 296 127 135 47 195 6 23 73 125 146 220 226 236 22 275 19 73 175 296 148 280 7 50 12 207 38 91 29 188 52 98 78 198 237 270 83 281 89 268 61 63 44 191 191 244 7 159 206 213 89 112 46 160 105 276 93 192 247 262 20 267 136 285 28 260 90 225 198 297 25 81 74 146 130 180 54 209 8 251 185 271 69 126 32 241 38 260 5 58 118 184 7 115 37 106 75 302 112 190 43 106 213 248 153 272 139 195 87 111 59 157 33 125 274 296 18 118 64 241 12 286 74 76 4 23 145 158 131 263 165 180 225 260 15 282 165 267 122 180…
Output: 3

Example 2:

Input: 911 910 1 911 499 864 388 656 109 562 99 667 23 444 25 550 181 218 395 627 325 396 230 570 228 878 28 225 393 816 637 662 51 680 373 417 440 902 671 788 326 530 45 723 438 722 82 744 236 862 657 853 255 620 120 361 576 744 497 714 109 784 854 898 54 58 339 413 63 96 257 553 225 331 716 865 63 536 441 553 5 170 151 301 135 850 381 686 623 747 563 673 446 569 441 749 267 565 7 742 424 553 341 572 55 419 543 890 491 624 140 567 278 463 143 602 80 791 111 315 131 592 342 388 442 551 75 325 515 545 406 693 41 146 562 826 474 782 219 499 45 118 98 732 406 838 545 851 646 835 151 483 297 566 284 509 109 880 764 834 427 704 94 780 512 593 402 834 589 909 121 686 559 777 137 269 35 733 432 588 522 760 61 777 511 722 454 728 14 703 61 720 596 836 803 883 114 197 208 457 226 855 377 905 3 590 594 757…
Output: 15

Example 3:

Input: 1126 2434 1 1126 411 995 133 497 573 751 24 990 100 940 56 1010 942 950 74 389 86 764 223 585 148 270 949 1063 560 1010 807 979 621 1005 642 1124 841 886 598 926 575 838 490 498 291 862 74 825 316 450 303 372 63 245 325 458 45 86 226 886 13 1034 326 813 189 277 50 943 494 589 201 1029 210 864 370 1090 712 1005 359 1092 650 842 259 1062 307 631 172 509 247 349 159 620 9 530 174 1069 997 1030 341 502 499 863 282 539 530 872 37 79 691 922 111 919 543 740 646 662 18 944 543 637 515 543 1049 1086 387 880 769 1013 46 827 191 1085 226 350 771 1090 97 193 73 138 389 617 894 1026 347 625 358 502 282 635 50 1124 175 732 123 544 30 845 143 593 738 1073 87 614 111 328 365 615 67 561 459 487 569 922 143 910 294 1054 20 877 17 824 150 464 640 937 230 926 1052 1077 113 581 31 442 431 789 75 897 391 1015 …
Output: 5

Constraints:

1 <= n <= 1483; 0 <= m <= 2966.

Loading...
Test Cases:No test cases
No test cases available.
Morgana Counts the tunnels - MEDIUM Coding Problem | CodeTikki