CT37067

The Fewest Hops Beneath Ashfall

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Deep in the ember dunes of Ashfall, Scribe studies rows of roads entries. One clean number will settle the guild's oldest argument. 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 <= 1430; 0 <= m <= 2860.

Example 1:

Input: 706 705 1 706 441 567 301 371 2 165 165 592 29 135 61 399 401 467 134 138 28 441 403 542 101 440 66 170 226 690 299 603 463 643 138 358 47 229 191 359 126 494 102 118 24 199 317 664 65 433 153 366 514 554 423 471 106 114 48 460 51 318 283 646 182 336 172 310 130 254 28 410 222 314 405 560 565 703 158 164 23 384 372 666 332 443 184 296 122 596 193 494 346 641 380 426 187 482 50 68 203 287 131 442 125 585 308 634 79 307 239 624 4 317 192 545 407 585 362 408 60 465 34 423 206 388 338 691 419 637 136 619 127 442 40 512 490 548 186 584 163 440 144 539 562 627 425 688 163 240 493 588 62 402 276 295 36 576 149 352 232 542 67 628 124 613 6 356 401 666 204 226 141 526 338 527 87 218 269 357 163 406 278 603 408 603 389 422 293 441 30 42 209 590 399 648 371 641 188 228 159 450 285 697 505 650 145 245…
Output: 13

Example 2:

Input: 186 519 1 186 120 122 79 148 152 158 84 110 117 142 97 118 23 70 85 126 43 60 15 169 7 81 29 37 77 102 60 179 57 71 41 61 61 133 54 116 43 121 63 124 144 158 51 61 50 63 9 172 89 183 50 141 87 116 69 90 142 170 2 78 35 162 71 122 40 175 130 155 20 113 71 149 119 148 57 95 59 161 116 153 19 92 4 130 23 46 91 133 146 185 76 84 71 109 95 122 75 83 147 157 107 118 70 102 117 143 110 126 25 172 115 135 54 108 30 150 10 182 39 145 37 171 156 186 146 183 53 143 10 118 9 18 36 51 52 58 90 176 28 62 50 173 89 178 43 67 48 125 62 169 72 107 44 94 30 186 124 131 11 163 96 174 7 146 67 167 78 141 64 98 52 148 14 23 35 116 20 134 72 153 38 82 50 73 67 151 1 97 80 149 8 77 64 91 12 55 18 48 37 60 93 139 125 129 39 41 114 165 28 77 28 48 29 168 134 169 99 114 20 107 20 112 24 101 32 97 91 145 7 110 38 13…
Output: 2

Example 3:

Input: 1204 1864 1 1204 410 1106 474 549 367 776 393 785 620 1042 262 626 350 777 34 626 294 387 121 640 492 1172 546 1127 178 625 54 258 347 528 842 935 402 887 830 837 123 555 214 1193 316 339 91 362 542 733 26 1091 608 857 62 750 568 1183 266 927 151 316 417 829 1164 1201 33 930 82 857 155 419 864 1010 215 404 549 1041 732 980 399 410 373 1177 729 931 149 422 938 1019 547 792 786 828 818 1119 395 1152 827 899 233 301 495 659 718 1179 113 750 774 792 131 711 31 953 76 352 439 1030 326 1113 656 1175 596 727 27 757 130 587 461 547 79 140 521 528 173 850 392 516 218 1080 534 743 287 519 82 817 331 1139 369 994 506 732 122 437 189 504 228 378 342 563 1113 1145 11 777 959 971 305 689 2 241 165 1092 298 683 33 515 671 1144 15 457 649 725 276 574 88 991 638 680 59 568 937 1104 104 303 1009 1145 253 11…
Output: 6

Constraints:

1 <= n <= 1430; 0 <= m <= 2860.

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