CT42183

Asha's roads Fewest Hops

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

In the steppe camp of Horselord Plains, Asha the customs officer keeps careful count of the roads. Settle a dispute between crews, every figure matters. 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 <= 3664; 0 <= m <= 7328.

Example 1:

Input: 500 1030 1 500 81 414 59 259 273 457 5 440 317 472 209 316 308 381 92 365 78 140 307 381 49 490 231 355 345 346 38 76 116 176 200 422 264 432 436 477 215 432 487 488 123 378 30 437 164 253 90 235 345 348 240 262 33 65 461 498 101 197 252 381 57 276 96 371 363 432 228 243 290 306 87 202 263 289 377 470 363 418 67 400 470 485 5 68 33 277 127 265 18 220 103 108 155 488 446 470 205 289 361 486 122 281 72 229 14 377 149 402 362 484 42 349 302 489 214 242 138 345 172 420 393 400 118 403 13 125 82 123 123 376 151 346 315 476 69 306 256 476 42 252 77 400 51 453 1 186 273 402 199 483 185 346 286 387 120 186 79 366 113 148 273 432 18 21 229 467 140 406 382 457 40 292 164 354 217 272 25 304 369 421 178 413 326 368 117 292 74 482 34 470 395 445 205 497 192 491 211 424 59 381 74 443 318 450 124 216 93 …
Output: 5

Example 2:

Input: 2777 3229 1 2777 893 1884 933 1119 763 1937 1979 2688 1045 2233 1752 2674 612 1333 780 1064 167 2188 520 713 2196 2489 1261 2174 851 1202 909 1918 973 2600 1357 1704 984 2766 824 2093 1952 2170 77 2448 923 2392 465 2449 163 1326 409 722 599 2491 799 2476 72 1223 1170 2462 10 153 1122 2107 601 2476 872 1542 1127 1907 1282 2437 1716 2414 1441 1476 1870 1880 471 1339 863 2430 755 1736 74 2550 2361 2711 388 1376 572 598 17 2332 2224 2615 2229 2634 1533 1605 1348 1699 1343 2513 141 173 715 1874 880 1078 1278 1860 575 1642 161 169 69 2195 1915 2574 1771 2416 585 2402 266 1685 150 972 1483 1548 2542 2726 1044 1528 10 1783 154 519 1332 1365 200 2545 1212 1468 1581 2586 1746 1869 601 2076 965 1651 1679 1880 1313 1624 2369 2741 114 1829 958 2332 1026 2031 119 249 2214 2393 237 358 1029 2351 1154 216…
Output: 11

Example 3:

Input: 1569 2908 1 1569 74 176 752 1505 942 1459 795 1529 733 783 4 845 53 254 396 835 375 1141 1430 1457 447 811 763 1510 792 1169 631 672 1113 1214 29 1391 90 431 543 687 1274 1466 874 1171 327 1366 348 823 218 1303 427 1381 582 1107 474 1215 274 325 657 1014 1490 1562 464 598 723 877 473 827 574 741 84 992 176 976 128 1206 253 1422 298 1346 935 1065 46 145 1238 1417 1035 1063 929 1236 1072 1078 285 588 1217 1283 672 1364 574 825 569 1506 748 1315 31 1081 170 1547 1031 1100 688 1005 1308 1512 1173 1325 123 155 213 1393 720 1173 255 790 70 1085 39 1179 302 762 1500 1513 81 609 1013 1034 564 872 237 318 1426 1520 602 919 41 1007 232 1445 9 793 278 1081 999 1479 815 951 154 276 26 1080 264 1552 199 489 321 1048 1134 1551 676 974 140 1202 166 985 473 583 402 1305 459 1210 1110 1534 747 1252 1197 14…
Output: 8

Constraints:

1 <= n <= 3664; 0 <= m <= 7328.

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