CT51756

The Ember Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Before the gates of the cinnabar mines of Vermilion close for winter, Wren must finish the bridges ledger - one figure at a time. 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 <= 1648; 0 <= m <= 3296.

Example 1:

Input: 673 2655 1 673 104 659 514 537 12 405 415 552 619 630 7 103 44 645 495 611 292 367 155 404 316 348 288 507 315 487 32 288 83 462 135 377 228 521 66 523 214 331 29 451 10 249 26 115 167 473 424 663 466 642 160 632 446 556 35 75 17 206 421 639 13 517 498 509 412 463 53 571 212 618 247 253 226 619 23 31 332 650 190 226 388 647 495 659 160 183 329 633 291 389 106 251 376 668 204 463 560 609 39 607 67 269 445 597 28 257 182 333 214 300 148 632 582 611 277 503 392 443 40 212 331 463 360 521 344 418 10 342 174 259 141 467 137 564 131 318 398 405 327 399 129 306 222 265 114 573 85 369 468 654 323 663 413 431 234 427 496 619 160 255 223 236 582 603 3 318 512 634 12 601 40 319 103 238 81 168 113 531 56 672 98 476 536 619 158 595 369 557 260 425 161 443 271 355 451 579 518 638 44 245 136 234 30 400 2…
Output: 4

Example 2:

Input: 1037 1933 1 1037 203 967 135 246 60 238 380 1007 652 911 565 775 13 977 391 1017 684 906 213 778 361 699 409 521 431 746 280 821 497 765 35 814 97 818 126 691 490 889 303 834 597 618 776 933 514 706 177 364 35 1022 68 585 592 641 216 940 68 120 216 390 99 1022 31 850 90 946 365 418 423 582 333 919 215 503 229 287 323 805 55 881 46 139 391 519 568 945 21 305 16 288 734 877 548 862 414 932 203 513 684 1021 13 569 674 733 679 702 27 1008 876 907 14 81 176 783 18 628 642 859 335 591 119 187 158 818 206 477 260 433 105 761 120 799 65 663 408 653 288 628 869 889 178 240 30 775 332 526 496 636 568 641 62 388 151 505 725 960 55 162 33 55 15 736 832 976 687 1033 126 451 413 475 549 579 210 433 191 358 215 636 462 755 552 835 471 808 656 1028 738 973 368 628 324 818 149 193 331 931 245 452 307 1017 …
Output: 5

Example 3:

Input: 260 3278 1 260 99 149 204 221 79 181 116 248 95 101 133 138 46 225 103 163 37 210 84 189 146 207 145 207 41 220 73 212 2 46 66 101 73 213 133 238 45 186 46 210 56 68 69 218 76 220 5 220 41 204 131 194 5 204 9 137 22 245 102 133 34 119 27 171 151 233 51 222 155 212 25 141 187 240 14 133 142 161 205 241 218 255 10 94 86 117 92 124 236 248 48 68 130 248 98 178 147 179 4 31 161 206 85 258 84 145 16 125 140 198 65 191 31 62 159 235 95 238 145 259 144 187 168 215 230 238 76 257 116 247 182 212 16 60 147 173 118 153 110 196 108 115 97 247 101 253 95 124 7 64 28 228 114 144 18 34 91 138 137 177 131 157 67 242 133 217 4 106 187 246 58 201 142 169 151 241 104 141 105 180 19 186 26 94 140 196 46 79 169 244 46 184 37 91 193 200 5 200 194 229 87 213 61 192 54 243 78 128 14 120 161 251 33 255 115 248 16…
Output: 2

Constraints:

1 <= n <= 1648; 0 <= m <= 3296.

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