CT45930

The Fewest Hops at Highreach

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

The council of the mountain city of Highreach pays by the answer, and Steward intends to earn it. First: the full register of bridges. 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 <= 1249; 0 <= m <= 2498.

Example 1:

Input: 360 359 1 360 183 309 110 244 138 243 202 332 28 74 63 157 93 137 241 347 98 178 102 307 173 302 92 298 120 164 39 95 18 203 58 256 46 265 37 184 156 292 141 147 47 255 120 226 311 316 24 140 233 321 21 97 7 161 201 210 36 297 105 182 93 140 91 147 244 338 68 291 241 307 125 137 301 343 58 192 107 117 163 337 27 352 74 200 266 358 169 264 122 198 128 306 117 266 33 305 110 307 65 268 84 93 46 153 314 335 138 262 258 273 194 327 12 113 50 215 148 169 134 293 13 151 38 319 5 58 146 153 157 239 14 166 34 336 62 254 59 356 122 191 49 97 188 329 76 171 80 186 14 225 206 251 222 316 177 246 204 254 235 289 123 161 57 304 98 117 110 294 108 353 27 327 83 116 174 202 77 347 127 192 59 249 50 301 169 270 183 301 38 320 9 336 30 291 214 347 17 95 42 104 237 255 15 326 72 358 179 255 169 356 172 339 …
Output: 9

Example 2:

Input: 1185 1184 1 1185 249 512 207 626 67 1167 85 294 700 1118 417 1083 206 498 656 671 65 786 255 333 203 908 758 1158 266 478 417 496 683 815 832 988 158 345 131 520 60 902 318 706 60 1037 271 455 523 966 228 639 844 849 333 334 389 716 460 603 896 988 41 177 471 1024 583 1084 313 995 530 874 250 1022 860 1102 9 352 657 775 196 518 286 681 1008 1139 12 1072 401 717 808 1004 238 650 267 946 119 784 306 444 237 252 808 1031 408 883 433 539 85 894 706 1114 635 863 272 916 221 493 249 1156 66 599 371 613 111 1054 321 786 119 213 808 941 814 823 283 859 278 1113 56 1124 685 1048 449 875 58 631 996 1054 271 368 973 1158 7 297 216 691 755 1004 431 552 240 975 480 824 361 550 182 819 111 284 820 871 461 686 152 527 518 1002 201 797 336 567 245 768 78 1059 283 1056 512 600 641 1094 156 432 485 966 1124…
Output: 10

Example 3:

Input: 357 599 1 357 90 234 112 315 104 175 41 185 67 335 79 332 41 129 57 299 27 309 196 336 97 98 17 107 50 64 285 292 81 288 218 322 12 279 43 255 138 146 15 38 51 223 119 196 93 136 317 319 123 209 18 227 61 300 60 262 65 214 78 253 336 344 3 311 20 180 205 207 99 194 161 330 5 319 33 313 38 143 84 330 44 300 35 69 119 129 106 161 87 323 61 280 44 49 23 346 77 220 167 174 188 293 143 164 107 310 68 313 126 192 253 310 55 241 67 286 141 209 64 310 104 194 6 100 35 53 250 292 199 234 79 126 82 228 30 268 90 320 12 175 107 176 45 246 92 162 174 345 100 195 141 295 104 303 200 351 2 248 129 139 139 269 166 256 154 189 119 210 209 227 19 61 241 311 92 124 187 238 42 279 233 302 103 328 202 241 45 81 24 263 68 291 225 235 78 250 107 174 32 185 91 219 220 256 107 160 77 334 26 242 30 36 75 239 152 2…
Output: 5

Constraints:

1 <= n <= 1249; 0 <= m <= 2498.

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