CT48293

The Fewest Hops Beneath Tranquil Basin

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Elowen inherited the workshop at the lotus ponds of Tranquil Basin along with its curious bookkeeping system for corridors. Time to make sense of it. 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 <= 3344; 0 <= m <= 6688.

Example 1:

Input: 429 1141 1 429 421 425 123 377 287 414 160 327 4 132 9 308 245 306 181 393 145 312 23 340 198 307 10 14 81 422 72 180 348 374 91 296 230 282 99 245 157 391 151 220 48 232 56 68 240 381 175 413 201 231 72 84 96 198 40 130 103 220 213 329 351 424 5 212 89 230 149 216 49 126 347 365 154 275 336 416 223 284 77 352 228 359 70 225 91 311 245 420 124 284 92 418 164 416 115 293 133 343 140 354 230 338 44 341 238 425 155 318 24 370 151 370 68 283 380 429 348 362 19 382 63 284 138 328 28 113 320 348 174 329 8 415 182 410 350 413 86 428 48 62 292 317 312 368 28 152 119 206 17 143 97 219 58 323 38 280 60 130 210 403 6 87 296 363 250 283 64 428 48 280 370 411 272 352 29 410 165 348 7 168 172 196 18 314 210 301 27 94 125 410 86 352 225 354 175 339 158 416 44 166 230 324 26 66 222 329 17 79 161 223 47 18…
Output: 4

Example 2:

Input: 188 4476 1 188 74 124 85 150 15 89 79 147 169 187 41 72 160 179 107 184 15 175 98 174 60 158 44 51 8 82 111 141 30 64 82 104 40 171 91 104 28 176 69 174 13 164 9 188 18 96 50 146 6 47 155 166 112 160 5 16 34 124 80 182 42 96 147 149 140 153 16 176 36 111 32 38 21 83 97 154 1 146 50 51 67 68 41 105 61 89 96 187 49 153 112 172 29 149 23 45 25 167 13 132 11 136 81 182 133 180 65 103 17 173 10 121 91 103 83 114 111 142 167 176 92 181 41 179 11 86 62 111 34 158 94 147 125 186 77 165 8 145 35 36 18 134 70 154 5 63 9 147 87 158 6 144 59 161 66 162 35 92 162 185 93 153 3 137 31 119 105 118 31 147 27 73 37 130 79 119 93 172 7 156 88 149 74 86 152 154 47 169 99 136 84 148 7 158 53 66 58 121 41 186 107 160 22 50 11 37 44 74 42 168 52 61 70 120 84 155 65 130 143 176 11 157 109 160 25 100 71 97 7 27 15…
Output: 2

Example 3:

Input: 1788 2698 1 1788 1258 1739 795 1310 235 1752 1275 1333 151 1460 467 904 509 1458 1358 1567 78 90 148 276 1084 1310 161 319 40 1080 1524 1578 471 1370 689 1164 1380 1633 468 1439 27 1755 756 1519 832 1451 32 1496 293 1341 1117 1323 909 1261 398 1759 293 1413 43 961 335 1608 887 1660 768 1027 61 236 1183 1678 558 1416 15 547 276 386 478 537 176 1622 371 888 14 1612 1190 1736 1117 1625 163 305 728 1657 423 1025 325 1381 766 1215 582 1201 116 136 198 566 171 1013 517 1082 932 1100 28 1527 73 87 895 1121 475 1366 42 1694 1087 1138 924 1653 538 1166 1054 1366 315 691 473 1097 522 859 213 237 489 1279 48 1303 122 1171 415 1205 509 1438 155 755 728 1611 942 1541 412 1346 220 811 1137 1370 376 1470 745 1659 256 1246 74 1680 1172 1597 500 1593 633 1677 421 1596 469 725 1303 1479 435 538 126 538 120 …
Output: 5

Constraints:

1 <= n <= 3344; 0 <= m <= 6688.

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