CT44658

The Fewest Hops at Frostgate

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Legend says the vault under the northern keep of Frostgate opens only for a perfect tally of routes. Porter 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 <= 2768; 0 <= m <= 5536.

Example 1:

Input: 2205 2204 1 2205 130 221 835 1094 544 1026 999 1167 673 684 685 1074 979 2097 1378 1638 110 545 1138 2087 1431 1648 1423 1631 673 1630 447 884 318 542 1289 1545 63 1387 80 950 104 1608 170 738 1927 2047 197 1908 307 1668 501 1215 1118 1518 168 1162 1022 1846 871 2068 2 275 1201 1934 585 614 467 1841 783 2201 731 1033 322 376 576 1552 1009 1896 383 1135 268 982 115 663 57 379 135 1262 1720 1871 896 965 867 1847 408 468 579 1598 927 934 839 1016 1216 2066 54 1333 1735 2027 94 280 488 1421 1147 1602 407 1221 377 1676 210 365 856 1589 330 1039 1390 2006 478 848 733 1195 682 928 306 482 526 536 1041 2111 692 1470 1175 1179 747 964 136 621 1739 1793 199 532 1570 1998 210 756 703 2043 314 1714 390 1106 1592 2080 1538 1877 867 1275 1010 2133 1548 1902 1226 1691 1206 1311 1904 1969 1964 2157 403 72…
Output: 14

Example 2:

Input: 1231 3998 1 1231 151 839 155 179 110 1103 593 625 427 941 544 968 599 1055 937 952 592 1228 10 822 176 930 31 96 95 170 443 582 704 1065 16 1119 927 1138 510 1101 226 444 15 309 158 803 819 1161 612 963 789 924 738 983 65 867 107 915 407 588 43 347 325 724 129 488 987 1211 414 458 438 597 523 997 95 456 473 1112 164 630 523 624 543 1131 137 309 579 793 662 1096 385 1058 277 756 456 1130 432 798 301 672 16 83 19 1216 243 855 260 673 809 982 206 1026 335 762 209 436 470 625 18 896 273 555 549 683 18 143 915 924 219 1230 417 1083 167 301 478 524 180 497 781 923 190 1125 471 1197 1060 1216 91 106 312 907 359 694 755 874 551 802 746 868 25 910 776 957 411 745 249 487 132 818 262 670 316 780 546 1099 541 715 449 571 276 995 142 1077 91 552 266 984 148 981 50 844 540 747 83 264 167 464 172 971 51…
Output: 4

Example 3:

Input: 1432 3101 1 1432 48 166 419 1290 489 1062 357 1079 214 465 905 1111 24 328 1154 1305 321 679 308 1046 1311 1313 279 309 236 470 126 477 247 676 828 1118 303 983 374 831 109 1057 27 708 295 877 141 722 960 1335 1057 1206 652 739 86 665 1385 1393 825 911 815 943 474 550 688 971 448 1240 327 632 514 1231 447 616 258 1382 507 1104 1126 1397 96 559 675 1072 209 515 298 1170 410 1297 1043 1427 145 222 951 1419 489 559 582 1066 554 995 474 1260 509 600 299 704 70 520 792 1249 553 672 10 1308 793 1373 558 991 578 1372 877 1268 799 986 1188 1240 428 1161 1173 1194 33 843 549 1227 730 1409 485 1339 248 714 166 215 602 770 720 976 12 200 34 996 693 1166 797 1423 714 868 230 677 304 1057 94 1011 468 1303 652 1178 296 1053 75 510 589 748 138 889 345 817 474 895 892 1172 453 603 288 1416 240 496 773 119…
Output: 6

Constraints:

1 <= n <= 2768; 0 <= m <= 5536.

Loading...
Test Cases:No test cases
No test cases available.