CT31562

Mason and the Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Mason the chronicler watches over the pine barrens of Needlepoint's stores of canals. 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 <= 1852; 0 <= m <= 3704.

Example 1:

Input: 1334 1732 1 1334 297 756 727 1263 556 652 101 1188 103 838 203 1118 354 558 604 1045 790 918 277 407 212 599 27 712 1268 1315 489 491 114 400 297 574 520 976 139 365 561 1124 427 982 1020 1104 977 1157 113 550 704 1123 593 889 488 1032 219 1034 29 1122 643 765 23 662 1015 1221 814 1270 479 501 684 895 106 1263 749 753 478 491 1160 1301 225 747 661 862 891 957 71 207 914 935 779 1172 183 1163 1125 1217 933 1159 977 1143 308 1091 1133 1137 93 238 352 1272 186 202 428 1053 251 772 36 1149 451 583 541 1216 303 658 1074 1193 628 1048 803 984 76 1173 542 888 428 1303 728 1022 8 1263 472 619 17 300 131 858 313 717 168 1316 636 833 107 625 375 1250 352 637 179 1007 529 1268 100 435 37 109 489 667 881 1192 127 886 282 1047 2 628 151 653 489 1280 13 194 2 303 816 832 626 1283 265 1079 173 1324 929 1…
Output: 8

Example 2:

Input: 1156 2123 1 1156 313 1149 359 986 490 1050 171 355 684 1118 176 592 639 738 60 544 63 611 189 350 844 1080 40 1145 92 945 91 541 134 547 310 424 73 1026 46 89 729 777 455 1147 227 255 152 610 709 991 236 380 253 1055 156 218 615 678 497 828 312 863 142 488 15 706 131 1017 977 980 617 988 815 1124 256 624 258 864 978 1067 21 588 488 1104 560 669 256 1069 355 871 29 116 487 1129 72 883 355 978 177 565 573 655 106 960 547 973 401 974 440 823 311 620 9 890 93 951 94 690 139 850 396 963 83 262 72 317 125 918 213 641 624 735 383 905 349 421 269 554 408 619 117 497 153 250 413 510 156 731 250 894 441 854 148 528 197 273 319 464 95 937 18 986 121 275 501 781 827 838 229 1069 129 470 62 85 17 169 585 1070 70 421 790 1050 448 479 106 721 356 543 605 832 49 1001 40 1125 478 831 98 547 161 958 214 259…
Output: 5

Example 3:

Input: 136 2840 1 136 68 80 24 98 4 9 94 132 48 87 51 62 61 125 12 74 19 99 35 54 5 97 56 100 49 70 50 115 57 118 9 33 20 47 26 132 28 77 38 68 21 41 15 28 31 96 89 114 67 94 38 130 66 115 113 135 60 101 38 58 68 118 50 136 6 79 5 49 66 132 92 126 20 67 30 104 7 89 20 75 9 91 31 85 2 112 45 47 7 26 70 128 32 122 79 85 18 86 111 130 27 61 53 136 59 87 42 107 15 135 9 83 4 63 47 99 11 132 84 95 78 115 13 106 68 78 77 102 71 78 38 112 12 96 28 110 81 116 20 24 5 96 14 75 43 60 5 61 31 132 40 103 75 124 14 73 40 133 44 53 58 134 2 106 101 135 17 88 18 80 64 102 7 119 89 124 5 40 44 126 85 103 83 91 88 127 44 100 9 36 31 70 22 38 40 102 73 84 64 120 114 119 6 74 47 128 34 65 66 114 30 115 61 77 68 122 20 29 23 50 13 40 107 133 29 85 13 90 47 130 9 39 101 136 129 136 130 134 31 40 96 130 38 63 39 92 88…
Output: 2

Constraints:

1 <= n <= 1852; 0 <= m <= 3704.

Loading...
Test Cases:No test cases
No test cases available.
Mason and the Fewest Hops - MEDIUM Coding Problem | CodeTikki