CT31118

Rosa's tunnels Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Rosa the bookkeeper watches over the clockwork quarter of Gearford's stores of tunnels. A careful computation stands between order and chaos. 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 <= 1542; 0 <= m <= 3084.

Example 1:

Input: 1001 1000 1 1001 341 830 81 220 671 685 206 370 846 939 580 729 406 721 18 592 533 950 661 999 455 834 232 818 24 136 420 824 452 706 332 666 21 52 656 843 151 944 292 860 727 836 279 565 345 827 610 995 911 929 300 414 160 199 52 250 30 216 55 490 108 730 566 701 467 520 134 300 94 142 685 796 217 285 158 504 208 410 548 849 312 738 712 759 108 709 53 97 204 491 836 928 268 886 105 738 309 726 200 328 392 726 329 974 164 774 322 534 738 918 330 844 149 957 378 983 722 872 832 865 726 828 26 99 518 626 497 685 186 774 150 723 626 980 147 489 686 762 171 298 643 937 370 690 116 666 265 434 509 745 60 424 271 594 854 989 188 313 458 546 66 109 545 754 18 33 111 700 10 57 4 293 535 773 200 485 153 337 439 530 723 865 860 911 255 626 204 543 492 545 310 815 895 959 308 403 20 559 382 427 194 6…
Output: 7

Example 2:

Input: 32 496 1 32 8 24 5 12 15 28 4 10 18 29 17 19 20 25 8 27 23 32 9 27 23 29 13 27 6 28 29 32 12 29 6 18 10 22 7 16 19 24 1 24 8 26 4 20 1 12 4 25 21 32 10 23 5 32 14 17 25 28 1 19 7 24 3 12 6 26 17 20 6 11 22 27 16 31 24 32 2 16 8 30 8 12 4 12 9 17 9 24 24 29 5 9 1 16 16 29 5 29 21 24 5 24 26 28 16 32 14 23 10 15 10 14 16 19 3 32 1 22 14 25 14 28 3 15 3 6 9 20 7 12 1 17 19 30 27 28 22 24 18 19 4 7 6 19 23 25 7 11 8 22 2 5 2 25 10 21 7 23 9 14 1 9 13 22 22 23 4 14 20 22 15 21 1 5 8 17 3 11 8 9 14 27 15 26 12 21 15 30 25 27 1 3 11 28 3 10 7 31 28 30 19 26 1 10 20 31 15 32 2 28 4 15 1 23 22 30 19 25 10 13 2 23 4 28 4 24 2 18 14 26 28 29 16 22 5 19 19 32 1 31 8 32 4 19 1 32 2 29 26 31 23 30 11 19 7 19 30 32 6 9 11 31 1 25 9 18 11 12 9 11 3 20 11 30 9 28 2 10 4 27 4 8 3 27 12 15 3 13 6 24 7 27 11 …
Output: 1

Example 3:

Input: 1394 1460 1 1394 624 636 235 374 808 1009 109 641 487 1054 290 1323 459 1350 128 1082 698 1265 523 731 469 686 101 152 813 922 42 1253 208 451 777 1047 31 195 160 184 494 742 1154 1380 862 951 107 554 438 863 1175 1316 597 729 139 146 463 784 660 987 863 931 834 1367 170 960 232 1161 800 884 20 1375 148 931 750 1199 323 946 467 1377 482 1341 707 745 53 1385 381 639 674 982 333 503 688 973 288 794 575 1208 1082 1377 34 776 27 450 344 857 381 542 337 562 602 705 82 1049 17 750 221 1170 245 724 311 401 515 704 7 964 300 974 174 558 176 1162 81 895 234 306 894 920 93 576 414 473 706 740 389 528 155 956 198 547 722 1368 1157 1187 128 785 102 1198 1277 1331 584 1136 585 829 125 958 67 1013 126 706 364 539 734 985 492 594 992 1270 729 1336 724 840 565 993 596 1325 434 1192 388 1219 626 976 922 13…
Output: 5

Constraints:

1 <= n <= 1542; 0 <= m <= 3084.

Loading...
Test Cases:No test cases
No test cases available.
Rosa's tunnels Fewest Hops - MEDIUM Coding Problem | CodeTikki