CT34047

The Fewest Hops at Rye Hollow

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Vera inherited the tannery at the gristmill of Rye Hollow along with its curious bookkeeping system for tunnels. Time to make sense of it. 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 <= 1096; 0 <= m <= 2192.

Example 1:

Input: 128 1215 1 128 72 112 10 93 87 98 29 128 8 59 14 20 23 120 66 114 55 62 69 83 54 77 5 90 23 128 21 108 4 33 51 74 68 77 8 100 40 73 12 48 67 85 26 41 62 81 106 126 7 87 64 105 6 42 76 104 41 57 28 85 4 119 42 82 45 110 2 114 41 119 10 12 19 72 29 106 5 33 3 38 31 33 3 93 24 27 23 24 60 88 8 112 81 126 8 66 30 114 53 56 20 85 13 99 70 92 46 117 41 123 114 117 80 100 31 50 1 72 15 59 29 93 3 85 96 112 9 123 57 116 75 116 42 94 86 102 59 127 46 99 20 95 42 76 3 8 38 50 41 44 36 97 11 45 92 120 94 122 44 76 54 71 23 36 43 75 93 95 72 101 24 93 14 105 37 75 24 50 43 60 30 56 1 97 18 103 8 21 10 14 104 118 49 104 79 126 13 70 12 78 44 115 5 67 7 72 62 72 26 94 90 115 43 114 114 116 23 126 50 123 32 83 49 51 9 86 54 60 59 83 33 97 7 22 5 60 13 116 107 109 4 46 97 102 46 101 12 15 101 108 92 98 1 …
Output: 2

Example 2:

Input: 446 939 1 446 104 376 342 344 105 364 8 86 230 326 53 165 118 367 172 296 263 441 249 407 389 393 103 173 334 393 56 354 302 358 11 86 324 365 146 417 236 253 214 359 82 375 135 250 182 417 176 203 64 161 310 358 31 152 168 304 292 376 115 219 190 361 4 274 198 200 135 327 42 403 71 362 8 324 98 386 277 373 225 287 104 191 150 161 242 287 44 316 14 322 299 342 100 364 111 261 208 385 173 232 191 407 179 200 133 380 65 124 231 440 188 299 190 353 44 198 227 428 154 213 303 345 105 130 5 260 136 335 5 178 162 164 142 240 141 254 246 423 36 137 4 55 144 400 63 107 141 337 146 364 125 224 273 390 177 242 85 179 36 229 226 278 117 367 18 423 141 315 387 395 52 286 284 350 133 379 286 348 160 268 184 268 175 212 28 425 68 168 262 402 147 360 117 182 20 25 70 111 89 126 205 251 73 125 239 306 272…
Output: 6

Example 3:

Input: 172 405 1 172 16 145 89 139 52 90 131 163 3 172 3 79 64 154 76 157 71 124 99 156 18 56 52 151 148 154 2 63 57 151 14 73 57 93 60 91 115 136 64 98 46 144 95 171 33 113 86 144 58 95 43 50 87 133 69 110 55 76 104 122 18 155 158 159 42 47 35 135 37 162 6 155 43 132 6 115 37 91 13 167 30 71 107 156 48 130 107 114 22 109 51 80 56 171 23 130 123 125 83 109 85 156 86 106 54 73 87 124 59 143 12 120 34 60 107 161 62 143 26 55 42 116 79 141 39 169 11 87 128 164 58 137 83 117 9 97 17 131 59 127 8 58 10 49 64 147 50 130 36 130 74 85 40 71 93 122 133 136 54 124 1 93 34 124 31 140 21 88 24 124 33 137 135 160 10 58 12 144 59 168 71 151 110 129 32 59 92 159 86 146 132 134 53 63 46 135 73 142 100 133 127 148 19 128 63 170 87 149 79 129 99 149 164 165 41 121 59 150 6 97 66 113 126 151 31 170 37 166 114 149 2…
Output: 3

Constraints:

1 <= n <= 1096; 0 <= m <= 2192.

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