CT32112

The Roving Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Gautam found an old ledger of tunnels in the greenhouse attic at the island market of Coralcove. The margin notes pose a precise question. 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 <= 1990; 0 <= m <= 3980.

Example 1:

Input: 1054 1101 1 1054 727 1008 5 820 319 542 470 831 591 783 456 583 168 357 354 815 905 1028 71 811 31 508 137 871 298 988 75 245 603 815 562 894 434 729 347 437 306 360 76 452 620 644 150 299 773 1006 137 605 178 322 745 895 731 754 240 591 426 659 537 690 912 977 222 590 883 896 481 654 223 428 701 981 632 689 119 397 680 1022 260 908 473 536 404 471 55 804 335 576 512 776 125 779 676 752 888 1000 223 313 554 614 805 994 440 623 388 604 172 1028 290 461 255 705 204 206 510 752 82 845 272 362 486 750 427 964 783 991 35 201 529 871 866 989 259 397 472 729 344 748 61 714 204 325 330 941 547 986 656 1042 811 1029 37 552 668 760 3 516 199 615 476 776 75 644 668 748 966 1037 622 716 433 689 74 953 573 830 468 715 522 782 285 692 263 834 132 584 486 594 460 753 603 1001 394 580 590 935 163 728 911 …
Output: 12

Example 2:

Input: 116 923 1 116 20 101 58 90 18 96 18 67 16 114 46 65 64 93 38 39 15 64 24 50 78 115 56 71 30 114 18 75 56 112 27 70 64 96 53 65 10 41 19 68 7 43 41 111 8 102 64 80 92 108 28 89 2 76 60 103 50 82 69 99 91 115 62 94 57 98 8 100 1 35 35 54 73 91 15 55 47 59 97 104 34 96 10 102 81 96 30 112 72 115 14 60 54 105 19 101 13 84 54 84 23 110 90 97 29 107 13 102 24 58 14 31 48 100 65 111 64 66 48 57 40 41 1 81 83 114 64 67 36 99 62 114 33 62 27 55 75 92 45 47 3 11 2 112 20 25 33 36 15 23 9 103 68 116 46 114 11 52 15 111 68 107 52 66 40 84 111 114 55 84 89 97 79 100 19 77 32 113 66 99 39 61 28 30 65 84 30 54 44 47 46 59 3 78 14 85 48 91 52 111 22 109 42 89 15 58 9 104 9 37 18 116 55 109 11 77 18 35 27 72 35 100 34 42 42 64 21 49 99 102 56 80 72 104 63 75 14 63 35 73 48 80 41 81 106 108 2 28 34 103 37 9…
Output: 2

Example 3:

Input: 1510 2477 1 1510 370 1469 168 371 608 1224 481 1096 728 1061 644 1310 307 665 299 1263 179 384 134 301 933 943 254 302 1053 1237 32 1188 467 1353 109 230 171 1218 459 1175 311 324 239 1118 431 1150 287 964 878 1468 710 1413 448 530 323 1194 990 1318 1071 1209 122 389 218 1288 278 1023 303 873 30 1147 110 386 304 948 530 1109 379 1168 818 1473 326 456 435 1429 602 1282 363 1251 950 1105 485 994 240 403 621 1368 227 966 2 1321 513 1257 252 735 363 1186 266 546 151 484 493 535 391 1248 450 740 855 1198 395 1311 290 761 252 1162 25 1388 96 802 93 460 176 537 933 1080 1205 1241 499 1436 196 1287 205 1377 1361 1403 503 767 517 1103 259 936 59 222 480 1404 934 1025 594 805 530 1352 126 1034 123 688 424 1416 361 983 411 910 881 923 1150 1466 1182 1380 890 1466 764 1142 206 247 1032 1132 91 1472 74…
Output: 9

Constraints:

1 <= n <= 1990; 0 <= m <= 3980.

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