CT52204

The Fewest Hops Beneath Stormrest

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Zoya the inventory keeper watches over the cliffside roost of Stormrest's stores of routes. A careful computation stands between order and chaos. 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 <= 2289; 0 <= m <= 4578.

Example 1:

Input: 60 152 1 60 44 50 1 36 13 16 9 60 11 25 48 55 29 44 9 18 32 41 20 44 24 28 30 58 29 59 21 23 40 51 5 25 1 43 3 41 32 58 23 30 6 11 13 23 12 44 41 46 18 33 6 53 10 23 3 16 12 19 15 35 20 31 36 48 26 50 44 59 7 21 9 10 6 24 27 52 15 39 29 31 5 21 13 14 21 46 12 13 33 56 8 28 1 59 26 57 19 57 26 53 30 31 43 47 2 19 28 39 21 58 4 51 2 27 2 28 16 40 35 47 40 54 10 28 9 43 28 47 43 58 20 42 3 59 37 40 7 58 49 55 5 49 39 59 40 45 27 28 12 48 3 49 3 10 27 33 7 45 1 58 17 30 50 56 5 16 3 46 1 41 15 46 7 39 27 42 25 56 24 39 24 38 26 39 3 30 3 22 6 58 31 46 31 48 5 51 17 22 16 60 7 47 2 15 23 34 33 60 23 48 5 15 10 46 35 41 4 32 26 44 17 56 5 45 23 25 9 36 21 34 5 22 3 58 19 38 2 55 39 56 38 55 41 55 13 42 5 59 23 44 44 51 23 28 17 38 24 50 47 52 9 20 23 41 32 37 10 55 33 50 27 30 53 55 30 37 35 48 …
Output: 3

Example 2:

Input: 1536 3984 1 1536 361 1302 1103 1167 321 698 254 1252 623 705 212 1128 66 1339 298 1527 539 1091 1279 1344 713 1348 101 180 498 610 634 1230 1206 1239 950 1053 904 1007 216 1278 32 903 865 1108 419 1201 860 1390 1 502 448 1391 349 1008 322 786 957 1242 157 1258 438 1435 305 586 375 442 632 725 467 815 352 1042 28 322 958 1353 1460 1499 244 1397 81 1254 517 1023 1279 1413 1 1494 1289 1494 625 1223 228 738 179 200 726 1024 639 642 873 1324 298 1046 199 791 38 666 166 1118 191 434 426 1459 38 764 547 716 10 74 1099 1462 135 501 390 1216 1053 1536 46 1445 441 450 906 1472 697 1398 304 1484 67 1032 667 878 999 1469 1266 1391 119 325 865 1323 1140 1266 639 652 190 719 223 600 66 1376 686 752 1165 1244 101 1084 1160 1422 318 846 138 1063 192 242 183 1056 724 827 394 1429 921 1130 823 1076 388 1023…
Output: 4

Example 3:

Input: 190 787 1 190 170 182 9 74 120 121 2 52 88 131 22 86 6 171 13 103 25 150 42 121 108 109 68 79 23 37 48 181 25 113 81 161 135 186 8 71 70 113 52 81 86 178 20 151 134 150 54 178 111 186 95 108 115 129 26 129 105 152 64 173 1 3 68 122 41 175 119 133 100 184 41 182 16 47 112 147 7 31 2 184 44 130 105 183 97 142 141 184 4 184 54 55 24 44 49 67 114 120 50 109 66 119 86 170 61 114 133 150 49 98 132 142 69 79 125 150 63 135 106 146 14 110 138 166 65 131 48 67 11 66 121 171 29 86 152 170 12 69 7 78 96 143 124 153 90 127 83 186 7 113 48 91 2 168 99 128 11 100 27 52 107 126 18 65 82 94 160 169 39 66 72 100 44 76 41 46 16 182 136 147 114 190 43 176 4 38 143 157 23 83 82 130 22 60 14 145 89 107 33 58 93 96 43 47 46 98 13 35 12 103 27 111 119 157 23 65 34 112 16 159 3 106 40 113 75 134 47 134 1 6 71 177…
Output: 2

Constraints:

1 <= n <= 2289; 0 <= m <= 4578.

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