CT29103

The Fewest Hops Beneath Briarthorn

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Sahil found an old ledger of canals in the customs house attic at the forest village of Briarthorn. 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 <= 1128; 0 <= m <= 2256.

Example 1:

Input: 268 1348 1 268 52 94 140 220 6 136 58 168 11 254 119 185 86 119 73 118 73 76 81 145 67 130 115 203 150 166 14 138 144 201 35 135 191 220 124 222 87 257 105 239 129 215 7 224 92 250 65 178 49 170 250 254 18 185 27 201 98 257 35 120 147 180 113 125 123 225 133 195 172 180 68 89 176 178 76 139 35 82 190 208 31 34 125 165 56 163 124 204 110 170 47 208 123 193 86 164 34 126 108 123 230 242 59 157 132 152 115 218 20 191 115 191 182 223 11 26 37 136 144 252 120 166 131 157 170 201 125 217 100 133 85 209 73 195 223 240 59 84 21 67 200 241 189 224 197 230 22 231 167 174 52 116 123 210 80 249 181 205 13 49 69 148 200 226 128 184 12 260 105 166 129 148 178 227 154 226 47 173 88 139 26 195 61 135 44 95 14 96 9 237 152 232 36 141 44 68 63 186 54 234 52 230 174 180 216 219 35 153 101 111 129 171 96 156 …
Output: 2

Example 2:

Input: 627 1206 1 627 112 288 229 472 231 361 351 463 64 426 217 622 417 444 157 296 510 561 340 583 183 433 156 608 73 224 37 231 246 310 443 507 168 460 193 507 10 228 141 224 87 243 33 274 162 533 206 394 18 269 102 528 258 401 221 611 90 467 331 425 259 417 352 608 514 562 3 408 25 174 93 574 4 20 128 355 217 241 139 570 388 400 4 456 190 402 361 370 341 393 414 479 227 511 188 413 100 435 391 392 227 321 175 340 207 357 183 398 573 618 205 212 65 609 373 537 103 453 320 399 149 159 397 618 104 616 131 428 341 386 135 579 88 610 314 436 131 288 285 464 183 285 177 453 165 184 323 332 428 604 150 479 209 625 380 440 201 612 274 550 43 534 1 343 192 328 136 357 111 204 239 254 468 591 36 303 505 584 61 396 64 374 229 586 481 582 140 450 505 565 42 603 361 567 366 610 255 342 61 282 127 185 238 …
Output: 5

Example 3:

Input: 223 1878 1 223 73 178 81 195 57 121 152 219 152 160 181 203 71 110 48 178 137 158 41 158 5 199 34 164 165 217 71 85 64 197 69 181 3 165 75 174 9 211 43 60 44 73 82 91 4 88 127 143 171 212 30 112 102 168 130 221 39 97 107 175 12 24 121 137 103 135 14 72 120 187 74 183 74 147 131 208 45 123 17 146 35 89 17 72 54 118 49 103 104 116 138 172 85 222 90 146 45 77 95 184 20 94 17 103 149 216 28 133 25 54 146 207 59 181 131 182 65 140 55 83 11 104 160 205 6 56 64 85 4 107 64 187 65 145 62 110 152 186 79 134 11 67 205 207 15 99 102 204 3 144 132 133 9 57 54 163 22 102 166 187 45 139 75 88 131 167 54 140 33 39 140 176 157 158 30 156 108 194 4 191 4 5 119 222 87 210 15 23 40 182 83 192 35 120 88 220 140 202 141 208 24 26 126 209 29 123 123 128 9 137 98 197 111 131 103 127 5 128 25 137 6 65 8 94 49 68 …
Output: 3

Constraints:

1 <= n <= 1128; 0 <= m <= 2256.

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