CT30995

Petr's corridors Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Petr runs the customs house at the obsidian flows of Blackglass. Today the books show a list of corridors, and the numbers must be worked out before sundown. 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 <= 662; 0 <= m <= 1324.

Example 1:

Input: 285 617 1 285 229 230 176 225 88 175 112 152 258 271 67 165 44 216 147 153 26 274 39 101 5 126 16 267 137 150 43 246 76 195 93 104 131 279 19 194 156 239 193 276 11 251 14 228 8 144 96 279 55 278 24 108 62 144 145 219 48 276 108 198 65 172 67 95 20 32 12 18 23 164 168 177 20 248 180 198 97 270 153 207 81 148 22 285 17 269 143 188 157 206 13 16 166 257 13 222 220 221 130 163 3 4 17 233 19 103 217 278 22 55 89 185 21 193 156 160 21 94 198 244 156 168 37 254 29 91 40 241 5 136 47 109 8 125 131 145 121 132 87 242 223 271 57 117 46 107 28 116 85 212 114 160 112 247 233 277 100 155 38 251 92 282 187 247 97 242 209 251 134 173 214 239 5 209 269 270 204 211 205 284 146 264 94 238 233 246 87 131 160 181 83 267 133 210 140 165 5 47 55 115 13 158 132 143 12 120 182 208 153 213 20 205 79 91 142 151 23…
Output: 4

Example 2:

Input: 393 392 1 393 185 311 13 127 73 305 111 117 261 375 62 194 24 131 368 376 119 209 199 282 295 350 63 386 84 113 223 285 46 149 173 198 5 255 190 237 234 339 23 320 49 273 238 362 65 284 309 320 48 160 37 139 196 232 76 222 301 342 135 205 89 328 187 293 303 337 204 352 11 281 75 287 112 261 49 146 9 174 352 367 33 328 298 369 125 221 178 305 112 349 149 371 13 33 111 358 78 269 247 369 114 294 43 243 64 138 32 295 98 307 7 146 116 333 49 392 162 387 172 333 182 378 239 382 4 224 74 323 262 302 40 120 28 241 9 132 225 351 77 222 247 377 135 149 90 278 144 275 156 216 34 221 145 382 352 373 204 353 117 321 119 279 56 147 118 375 215 297 143 333 217 245 216 259 62 370 15 163 283 325 121 337 183 346 155 224 10 341 97 155 115 258 108 211 363 392 104 315 160 328 6 16 52 349 94 174 100 269 282 33…
Output: 4

Example 3:

Input: 356 889 1 356 190 222 3 334 216 224 277 278 39 147 164 317 145 340 96 319 78 293 233 279 22 309 33 348 7 153 117 231 160 162 75 104 86 172 200 278 137 340 41 182 13 280 86 180 110 297 215 350 153 323 20 155 15 87 43 70 151 182 175 199 288 329 213 231 49 89 227 312 202 215 187 304 74 184 133 240 135 184 218 231 168 344 174 275 142 250 34 55 48 318 210 311 91 219 127 256 202 331 141 181 141 165 12 252 257 353 171 256 143 276 59 166 129 144 53 350 199 231 68 229 30 189 12 291 169 275 212 339 17 159 138 339 26 164 251 303 113 318 107 147 53 107 118 184 83 152 203 346 106 283 6 198 51 325 49 297 40 262 162 319 19 57 34 250 177 203 51 155 17 184 111 295 292 319 268 336 87 343 40 52 42 221 158 284 122 230 283 323 223 321 27 154 21 249 24 339 191 194 179 201 73 106 287 341 150 175 10 203 61 190 25…
Output: 5

Constraints:

1 <= n <= 662; 0 <= m <= 1324.

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