CT32201

Wren and the Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Before the gates of the mining town of Ironvein close for winter, Wren must finish the canals 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 <= 1634; 0 <= m <= 3268.

Example 1:

Input: 683 1501 1 683 292 636 352 665 420 670 168 327 488 554 508 634 391 457 418 450 174 201 6 220 660 678 36 127 229 562 290 341 108 430 73 254 209 376 386 644 333 477 130 578 164 382 303 615 344 460 245 640 324 639 322 520 308 344 12 424 212 654 68 502 178 195 7 336 109 266 472 489 211 356 283 519 147 528 271 601 233 379 165 356 303 542 75 332 364 434 351 478 46 112 311 598 281 301 185 187 94 613 299 655 74 393 92 344 384 415 229 617 203 317 287 589 80 589 411 439 155 240 198 480 202 408 32 256 174 287 82 521 437 660 48 280 330 632 102 212 414 662 80 228 69 374 552 598 168 276 375 495 8 605 121 407 109 579 328 545 120 262 96 676 82 266 231 603 161 579 297 678 634 651 52 419 41 436 263 462 57 419 367 503 72 574 31 98 57 391 545 551 189 592 410 674 125 457 80 321 552 595 541 567 72 311 79 679 17…
Output: 5

Example 2:

Input: 1583 1582 1 1583 132 1468 1155 1246 56 304 165 387 1268 1345 1154 1414 196 1006 504 808 1217 1478 503 1151 959 1391 200 1108 254 278 645 1535 235 1437 554 910 1063 1434 1343 1347 502 814 252 510 668 784 826 994 655 685 350 526 1450 1460 18 1020 120 327 342 412 9 1346 257 405 53 374 540 564 623 788 450 728 953 1095 628 1039 15 1082 1020 1326 891 1578 465 743 1021 1488 309 733 322 547 799 1560 101 1155 1047 1456 346 985 101 1437 329 1055 24 1077 139 1343 112 557 550 1474 263 1184 615 1325 1412 1549 362 783 221 1395 463 1381 405 528 795 1406 248 343 424 701 211 974 554 1276 258 1138 950 1541 888 1255 1083 1136 696 1357 874 1444 751 1105 742 1531 913 945 614 771 557 1390 57 1474 480 570 890 1535 50 216 1254 1305 358 613 344 1420 525 790 835 1464 69 548 237 1498 702 781 849 1091 393 488 880 135…
Output: 11

Example 3:

Input: 1057 1056 1 1057 56 272 283 658 351 383 356 442 427 548 20 305 104 401 606 1006 80 276 194 848 22 315 400 866 787 1048 355 372 367 679 28 704 118 441 321 549 533 892 474 898 444 828 668 1035 51 370 556 1016 51 890 3 855 349 600 431 769 168 275 425 769 235 785 722 784 519 1019 471 648 616 1052 549 814 374 590 408 648 329 562 958 1030 174 636 437 452 484 775 678 882 145 796 118 873 717 990 434 535 11 17 129 728 8 499 53 537 149 1017 101 1003 342 771 6 1022 447 990 232 854 183 803 390 564 102 998 61 882 342 531 101 839 43 918 111 140 519 593 304 409 690 696 42 69 306 393 406 635 869 1018 122 473 777 781 140 608 73 418 317 1014 723 767 274 420 346 650 681 922 175 408 65 682 159 492 442 727 521 653 544 629 492 686 168 603 311 650 270 959 38 990 72 1014 147 726 516 1010 495 603 111 796 298 363 4…
Output: 9

Constraints:

1 <= n <= 1634; 0 <= m <= 3268.

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