CT32428

Caramel tunnels Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Before the gates of the eel marshes of Slitherwick close for winter, Minstrel must finish the tunnels 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 <= 1896; 0 <= m <= 3792.

Example 1:

Input: 1894 2740 1 1894 851 1747 196 1413 774 1825 1122 1385 151 1868 615 1628 1057 1829 338 624 151 1004 32 1542 1011 1248 1243 1797 220 1012 297 680 104 838 481 999 978 1295 1122 1705 428 1192 519 1028 646 1496 282 299 385 1712 261 574 722 1725 885 1076 1135 1160 121 619 1005 1738 490 1679 883 961 767 881 242 739 492 1051 492 1030 115 650 832 1156 611 1217 365 1473 423 884 715 1768 386 1555 1097 1098 1283 1375 1077 1237 647 1255 491 830 1254 1540 498 1318 306 513 1332 1886 791 992 41 501 1349 1637 1441 1631 464 1310 1408 1706 103 1128 649 1046 1395 1421 1150 1715 562 1285 516 1082 531 1461 223 822 178 279 337 1823 324 1193 217 247 752 1498 1228 1252 638 1042 1316 1517 1343 1424 1390 1829 1696 1792 61 477 990 1191 306 1029 93 363 499 1268 1122 1610 1295 1505 134 1421 442 1879 161 1634 108 1049 1…
Output: 7

Example 2:

Input: 598 3773 1 598 152 357 281 553 434 548 153 505 455 513 52 466 286 293 153 382 115 246 156 348 395 439 510 547 438 566 308 416 390 529 241 343 369 543 103 263 458 578 11 168 328 411 150 325 205 479 317 466 168 502 214 245 127 427 173 214 70 534 49 522 325 351 417 423 295 492 194 425 243 352 41 434 319 479 104 236 349 477 48 409 245 350 54 344 159 290 534 555 243 356 66 179 188 521 185 597 87 237 45 79 265 468 216 477 50 185 255 523 148 396 29 341 207 498 211 542 391 528 46 95 150 218 258 544 303 594 515 520 158 432 212 552 246 518 212 266 390 430 211 541 533 578 295 580 154 575 407 514 254 446 23 231 83 464 402 448 34 361 206 429 3 133 207 420 411 552 269 359 154 412 371 444 386 419 518 573 115 142 27 510 116 418 71 435 43 534 219 454 138 522 369 376 218 335 392 548 50 559 370 473 3 303 68 …
Output: 3

Example 3:

Input: 1456 3155 1 1456 20 374 705 1136 351 1395 389 1292 112 1144 94 1034 402 1237 736 829 692 771 76 100 1039 1096 1064 1398 110 930 1082 1259 431 793 70 1106 407 496 741 1302 380 1013 726 1099 404 1313 1070 1425 645 984 805 1251 483 508 667 1444 606 1155 43 1109 113 1078 65 102 83 435 144 1453 161 1225 956 1162 842 1207 1041 1403 48 910 1057 1067 129 219 130 1155 637 943 432 803 121 1258 38 1395 1134 1260 336 530 92 888 295 748 356 672 64 560 880 1183 1003 1273 978 1220 116 1376 572 936 812 1061 1305 1456 1152 1324 692 743 1101 1141 177 515 348 1436 129 1254 140 418 43 885 698 746 1158 1389 616 1154 847 880 41 758 238 316 386 618 124 616 108 364 507 1439 652 1154 819 1341 1124 1312 1116 1322 669 995 852 1245 991 1130 344 524 1300 1332 804 967 984 1170 445 1253 786 916 107 622 251 711 412 1424 …
Output: 5

Constraints:

1 <= n <= 1896; 0 <= m <= 3792.

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