CT29448

Lamplighter's corridors Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Morning light hits the monsoon port of Rainhaven as Lamplighter unrolls the day's manifest of corridors. The tally will decide the next shipment. 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 <= 562; 0 <= m <= 1124.

Example 1:

Input: 492 744 1 492 229 478 235 316 170 183 118 430 58 174 2 449 43 90 33 253 147 469 158 480 91 357 17 469 100 113 124 446 193 359 92 337 197 395 104 270 263 471 42 417 353 406 126 147 184 245 40 340 227 348 122 377 62 314 183 368 194 359 421 487 269 402 148 421 20 103 61 316 65 320 43 454 18 45 53 437 109 144 157 195 80 142 201 389 147 443 68 84 103 393 197 368 190 376 388 407 180 357 187 193 86 245 151 170 41 91 262 379 174 468 273 344 57 265 209 462 24 244 163 166 38 307 102 130 315 318 192 194 141 416 6 84 175 459 39 287 231 328 20 53 258 478 55 452 68 394 2 207 29 314 334 405 198 358 136 403 214 473 242 419 144 192 135 201 321 454 380 474 209 234 37 182 348 400 83 425 64 235 7 450 80 374 56 468 210 248 275 392 377 453 151 169 29 48 409 433 8 259 75 299 146 475 436 463 257 392 150 434 122 3…
Output: 6

Example 2:

Input: 344 343 1 344 102 125 124 265 174 275 112 168 24 35 14 66 14 97 49 104 12 58 108 257 96 240 204 315 33 245 125 163 206 249 45 266 198 322 10 79 9 196 168 226 216 335 81 281 97 118 136 157 61 297 68 303 104 305 46 116 142 279 104 285 153 320 111 203 183 262 83 166 185 279 117 339 21 146 5 344 17 44 41 251 155 177 113 179 305 337 306 317 62 256 59 84 24 131 65 139 116 171 172 231 190 334 257 287 167 254 168 221 250 279 28 315 5 70 97 318 126 143 46 62 20 191 140 258 77 246 45 332 15 187 84 263 3 8 114 204 104 323 159 275 305 312 30 198 95 316 78 211 55 230 187 296 96 180 31 322 155 271 34 205 205 228 85 104 220 315 89 96 104 268 58 110 279 327 169 170 105 235 144 299 80 221 251 278 65 242 123 324 36 226 69 166 23 62 158 182 6 280 162 277 279 333 35 305 33 45 199 338 11 113 37 133 116 133 72 …
Output: 8

Example 3:

Input: 310 580 1 310 178 298 37 303 52 84 87 270 175 284 150 295 53 259 111 307 174 202 177 215 55 59 186 251 119 196 66 218 15 110 111 273 104 115 129 299 33 195 98 214 185 234 56 244 11 233 162 185 17 73 121 210 228 268 19 93 79 227 137 204 45 109 65 101 176 251 162 197 49 221 162 263 40 278 162 235 134 153 138 151 205 240 23 98 44 95 226 240 81 122 146 230 38 98 40 47 13 134 243 279 123 188 7 134 77 81 150 215 85 213 278 294 45 285 5 217 15 175 23 85 108 253 287 305 30 113 101 123 42 212 164 260 24 190 220 279 46 299 176 229 115 231 174 284 105 156 54 223 67 253 29 46 223 274 60 233 232 251 231 258 31 295 48 247 81 197 119 120 182 264 200 218 185 301 67 218 133 273 60 242 75 204 79 124 138 171 39 214 12 297 104 226 86 179 18 147 28 290 147 200 90 193 116 289 8 230 61 154 54 247 27 110 123 281 …
Output: 4

Constraints:

1 <= n <= 562; 0 <= m <= 1124.

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