CT34556

The Masthead Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Nora runs the apiary at the galleon yard of Masthead. Today the books show a list of roads, 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 <= 1323; 0 <= m <= 2646.

Example 1:

Input: 507 710 1 507 260 375 224 419 211 221 10 420 80 464 100 238 76 286 29 104 421 445 74 328 211 495 173 255 198 462 31 345 141 346 243 364 62 361 186 329 281 410 26 255 227 286 158 329 275 325 219 388 40 211 431 493 41 304 199 499 234 309 9 40 194 224 113 137 164 281 24 119 89 277 204 494 16 204 93 301 95 297 43 106 110 478 52 129 354 365 149 353 92 318 21 220 96 441 6 253 71 82 257 379 89 478 71 382 302 367 47 476 31 79 165 375 125 163 380 503 284 381 274 461 351 485 111 346 161 209 32 395 224 426 393 401 117 318 322 374 435 452 289 377 9 424 198 226 178 228 172 319 55 318 30 441 166 499 83 159 148 422 38 434 115 248 46 425 159 252 237 481 109 315 210 464 210 404 33 35 153 212 100 123 437 463 62 364 383 409 116 229 344 507 91 423 239 321 279 442 280 331 52 376 322 394 89 239 309 390 72 233 3…
Output: 8

Example 2:

Input: 1073 1151 1 1073 21 605 813 831 435 436 364 837 473 936 833 935 127 312 846 882 191 426 2 375 236 657 639 840 253 299 159 325 300 895 972 1024 388 991 164 656 843 852 443 790 249 578 951 978 226 611 407 1055 240 661 128 786 661 765 106 769 361 1039 320 1033 246 500 405 911 425 847 374 686 392 497 129 269 782 863 396 574 195 279 32 64 59 926 208 534 376 932 306 898 406 458 23 301 641 682 502 947 13 461 557 835 578 881 404 971 154 1028 589 858 551 750 278 562 964 1020 42 110 416 884 734 787 892 1030 62 224 86 379 418 586 16 340 438 857 148 778 102 803 580 684 750 891 477 714 520 522 224 440 559 616 613 758 568 797 294 581 498 850 66 152 98 319 96 662 410 705 521 849 50 470 101 500 87 606 663 1062 168 936 178 862 453 1028 276 553 754 1067 138 253 123 152 279 807 379 992 197 294 204 913 761 76…
Output: 12

Example 3:

Input: 1287 1286 1 1287 1179 1273 557 902 205 1014 971 1244 368 1029 546 1156 405 1258 148 571 2 203 224 758 620 1171 216 1133 377 632 158 237 564 960 453 694 1101 1180 844 1267 346 450 402 969 85 985 4 298 1173 1239 1041 1177 426 907 932 1239 122 562 69 1194 680 736 595 782 216 244 209 1126 413 886 454 1106 886 964 547 1043 38 128 33 729 499 541 605 979 425 439 671 1144 148 1016 77 890 211 994 87 979 350 1226 326 884 167 403 631 987 498 1233 692 1162 276 468 541 848 651 1152 740 865 174 1033 72 834 1095 1236 285 493 163 203 112 181 249 540 741 1081 514 1068 130 457 164 1268 322 996 887 1173 412 1195 481 1209 34 385 289 1004 400 730 452 1080 492 914 279 886 232 1241 455 467 299 760 6 1067 35 147 329 1106 1055 1106 1009 1083 963 1193 55 1254 96 463 527 1188 425 1049 395 699 56 1093 770 951 815 992…
Output: 12

Constraints:

1 <= n <= 1323; 0 <= m <= 2646.

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