CT40888

The roads Fewest Hops Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Keeper found an old ledger of roads in the gallery attic at the copper works of Verdigris. The margin notes pose a precise question. 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 <= 3354; 0 <= m <= 6708.

Example 1:

Input: 274 4673 1 274 108 204 140 210 108 139 127 145 19 209 40 72 84 195 12 35 188 206 7 259 9 113 51 127 82 258 37 152 35 235 249 260 188 218 104 191 21 99 120 149 4 106 207 244 4 124 167 242 77 196 199 240 95 274 63 151 171 266 115 215 168 186 30 212 60 236 53 234 15 127 206 232 204 229 78 241 17 36 9 105 11 219 26 74 187 196 106 159 252 264 26 30 105 141 169 182 91 267 131 170 73 153 28 95 190 243 29 60 170 240 66 180 156 189 40 251 53 216 195 258 29 182 188 246 110 143 10 122 20 80 193 222 23 188 175 253 70 153 70 74 109 130 49 94 59 107 56 196 54 59 45 131 149 192 147 193 144 246 193 206 226 262 136 182 31 260 35 62 166 220 44 149 19 189 89 113 151 199 39 135 3 205 185 253 38 123 109 218 51 174 114 116 112 272 7 121 91 168 92 243 24 39 5 113 139 154 25 98 165 214 163 260 186 258 54 231 147 …
Output: 2

Example 2:

Input: 1318 4708 1 1318 317 1280 47 1169 672 834 128 992 947 1210 894 1243 180 692 122 532 698 804 88 810 304 987 80 206 1074 1171 354 1314 79 858 55 773 1062 1143 1098 1197 901 917 231 268 573 830 1048 1049 764 885 204 1044 186 809 261 1031 114 140 248 792 795 1317 240 1195 330 774 659 986 210 738 922 1141 29 258 548 993 132 538 975 1317 190 708 458 745 130 679 414 460 810 1283 992 1248 927 1286 769 1279 294 1041 490 1077 37 1179 1176 1245 632 847 567 1116 91 611 396 667 781 1091 380 612 371 1105 128 1288 939 1081 721 1288 1042 1271 746 953 1012 1020 327 720 147 1055 332 768 726 1069 252 546 580 1310 453 1063 570 1244 520 1068 361 449 218 1056 336 1200 13 1002 457 927 214 822 436 1276 145 559 179 772 259 780 207 1121 361 729 833 1056 148 1135 515 1170 315 397 348 968 472 862 528 897 697 1072 159…
Output: 3

Example 3:

Input: 1186 2450 1 1186 498 511 664 1153 206 845 384 857 348 630 1130 1171 513 900 187 214 364 368 185 451 812 898 72 445 232 551 389 559 361 736 603 736 226 823 831 892 11 438 533 575 468 530 328 666 310 970 613 716 340 987 1124 1136 874 1115 952 972 410 1056 21 1105 222 1171 130 817 295 468 594 653 377 672 714 1020 522 912 885 1106 339 932 1130 1135 710 1177 213 1058 492 803 945 1010 271 883 20 519 243 462 75 703 317 726 88 167 59 626 311 878 195 530 310 614 551 948 753 1091 1005 1109 113 599 21 54 223 964 156 1154 316 1149 193 495 512 724 852 1041 69 277 40 734 1109 1186 78 191 84 935 700 1133 638 931 477 512 939 1069 911 1104 105 899 221 949 640 716 346 594 26 661 625 850 597 663 527 885 449 668 491 704 188 762 422 764 377 1034 383 1044 383 578 712 1103 179 1041 559 720 433 1154 3 1063 255 60…
Output: 5

Constraints:

1 <= n <= 3354; 0 <= m <= 6708.

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