CT33969

Clerk and the Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Legend says the vault under the otter slides of Sleekwater opens only for a perfect tally of bridges. Clerk means to find out. 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 <= 934; 0 <= m <= 1868.

Example 1:

Input: 317 883 1 317 229 245 27 46 211 285 15 247 160 266 56 100 51 218 71 288 182 256 176 277 13 188 89 247 182 240 106 240 36 222 224 246 103 171 15 70 145 275 2 306 18 65 162 308 243 316 78 128 32 275 116 144 75 112 53 121 224 313 191 198 152 204 39 291 19 124 125 214 150 157 153 241 127 225 20 260 88 127 57 97 60 222 20 225 211 292 54 107 113 251 62 181 47 297 17 65 164 183 244 262 46 243 208 239 173 223 112 264 63 115 225 294 121 257 214 287 32 81 33 159 213 216 111 310 115 249 104 201 13 36 56 231 128 234 193 221 274 303 227 257 186 301 90 111 34 115 9 210 22 61 45 100 108 237 133 209 27 174 145 262 139 151 117 269 28 182 14 122 22 88 146 260 53 69 192 302 66 89 45 187 184 253 157 190 72 110 145 193 41 239 213 261 67 181 26 162 26 31 189 297 301 305 216 302 120 126 110 301 241 304 179 192 1…
Output: 3

Example 2:

Input: 755 754 1 755 586 742 447 474 343 528 614 647 138 316 332 695 181 511 558 677 15 376 134 333 459 490 232 596 225 441 313 746 107 586 579 637 207 487 69 376 531 707 409 732 182 570 192 580 439 480 197 298 261 409 258 515 118 555 623 694 259 694 218 548 517 602 58 716 313 412 159 422 154 732 31 634 340 411 147 289 43 620 32 240 605 695 6 471 84 449 418 686 398 719 94 518 517 664 75 263 92 303 92 621 52 410 409 542 28 692 393 734 364 689 113 314 49 338 308 542 442 560 37 499 199 661 455 746 266 416 174 736 143 166 212 738 116 162 348 498 2 686 273 709 373 686 195 576 311 584 348 419 96 708 205 396 177 441 83 392 57 745 25 646 596 705 51 205 227 629 188 584 75 252 1 693 642 677 202 241 6 255 582 621 6 25 542 689 610 671 157 431 456 604 10 604 280 683 171 467 82 328 54 440 92 329 265 540 249 74…
Output: 13

Example 3:

Input: 90 1314 1 90 14 81 5 21 15 57 48 82 84 88 70 85 20 71 23 53 40 81 29 31 15 83 35 73 35 54 33 45 19 24 13 32 3 8 17 38 41 61 8 38 21 66 16 23 48 62 5 59 17 79 15 62 5 23 55 89 2 65 23 71 18 48 53 70 10 18 19 25 56 65 36 72 31 56 31 61 18 53 15 39 38 74 22 41 5 50 17 39 21 67 16 71 80 83 23 65 8 43 11 46 54 65 71 74 37 53 22 37 12 47 61 81 44 53 39 88 57 63 8 82 13 82 81 84 43 55 37 52 59 67 3 46 2 24 1 14 31 35 5 84 65 84 7 36 28 83 53 58 2 79 59 80 58 90 30 39 39 56 35 52 19 63 11 64 52 79 4 90 5 65 30 31 11 77 55 58 50 67 64 73 70 89 28 50 48 87 28 64 72 90 49 52 33 83 12 25 38 81 48 80 52 60 74 90 11 52 52 58 17 76 6 38 55 64 85 86 27 74 71 79 9 60 13 51 15 50 54 58 17 48 5 85 2 31 33 44 32 71 87 89 23 75 35 56 7 86 55 88 18 32 1 71 12 64 15 24 12 81 26 51 61 62 43 69 8 32 19 26 28 32 61…
Output: 2

Constraints:

1 <= n <= 934; 0 <= m <= 1868.

Loading...
Test Cases:No test cases
No test cases available.
Clerk and the Fewest Hops - MEDIUM Coding Problem | CodeTikki