CT33024

Quartermaster's roads Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Quartermaster the clerk watches over the basalt cliffs of Obsidian Shore's stores of roads. A careful computation stands between order and chaos. 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 <= 1679; 0 <= m <= 3358.

Example 1:

Input: 742 741 1 742 297 362 495 680 111 330 2 518 258 274 269 714 505 659 147 506 595 653 245 618 359 666 48 456 467 650 105 722 285 687 117 394 128 695 12 446 267 497 308 619 35 602 396 512 449 508 73 234 90 454 536 562 200 692 24 500 442 650 245 492 322 495 196 638 297 539 513 521 241 334 318 731 115 404 511 543 197 346 130 693 30 144 448 679 213 481 67 465 341 365 204 648 70 738 582 634 117 403 112 620 701 730 397 662 221 321 234 327 126 148 629 738 115 740 262 341 331 742 435 481 501 552 104 549 287 541 277 415 372 729 487 489 28 94 167 560 330 553 261 385 20 517 158 508 283 427 220 551 75 87 42 394 161 368 498 588 513 693 154 366 255 736 109 413 105 231 31 671 411 422 304 327 512 526 25 215 58 566 125 660 261 358 29 295 183 220 9 305 79 388 507 542 141 342 192 367 286 323 43 505 543 633 94 …
Output: 8

Example 2:

Input: 711 1195 1 711 398 425 464 583 134 619 57 549 592 607 89 398 396 552 72 149 362 679 423 548 164 300 48 274 290 500 68 117 145 460 454 575 123 608 139 192 91 578 55 590 252 632 204 607 220 378 142 355 370 625 318 572 133 516 475 646 20 347 95 526 444 454 203 673 555 703 379 699 215 395 548 582 35 370 313 318 196 339 480 686 126 327 24 111 11 677 307 494 173 279 8 218 28 685 568 598 68 494 668 706 163 196 319 525 44 648 138 458 182 315 64 455 51 565 466 654 219 530 458 614 332 694 227 348 453 676 354 616 305 321 401 470 88 435 202 573 253 570 174 425 26 119 129 652 51 429 2 193 11 628 475 570 142 600 478 499 245 651 145 247 318 646 403 644 300 628 284 345 104 585 184 631 30 442 67 415 159 654 207 443 168 284 270 447 85 533 315 600 111 589 103 586 29 302 150 170 326 462 282 484 397 590 152 59…
Output: 8

Example 3:

Input: 165 1253 1 165 19 44 97 116 20 26 101 116 10 75 29 116 9 119 33 114 49 149 43 69 53 73 7 39 11 66 65 149 51 122 76 126 119 131 67 87 113 136 68 97 82 155 34 76 57 70 40 89 50 163 88 150 88 124 96 165 131 139 93 124 102 125 99 131 92 155 77 136 96 144 16 132 62 95 42 137 130 165 8 124 38 51 45 99 95 140 16 70 10 16 33 124 8 99 77 139 109 128 12 50 11 26 33 106 67 89 59 135 8 62 7 105 70 116 10 28 78 97 139 154 67 90 84 97 84 150 16 81 7 26 142 165 48 138 63 125 74 91 136 147 98 148 84 121 28 35 63 106 114 162 7 42 10 36 49 146 2 15 84 155 58 87 29 34 67 70 71 131 115 126 92 159 4 91 36 69 38 95 7 84 51 58 12 33 60 76 9 23 14 54 79 111 1 162 15 149 65 113 8 100 74 124 41 157 51 108 68 152 31 125 33 121 28 109 135 150 76 122 18 46 33 69 3 64 103 115 91 136 27 132 39 107 130 132 108 160 89 124…
Output: 2

Constraints:

1 <= n <= 1679; 0 <= m <= 3358.

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