CT30106

Twilight routes Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

Odin found an old ledger of routes in the greenhouse attic at the poppy fields of Scarlet Plain. 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 <= 948; 0 <= m <= 1896.

Example 1:

Input: 263 1062 1 263 13 197 114 229 84 255 144 239 44 193 140 178 57 144 35 77 33 89 107 168 80 97 73 126 13 137 115 188 148 168 13 41 104 125 148 172 10 227 94 124 69 189 197 202 191 258 126 171 18 203 96 242 38 169 39 57 70 130 96 115 167 236 10 82 186 244 27 263 32 228 34 84 170 195 174 219 60 132 10 44 141 202 70 259 86 93 2 229 83 201 38 252 28 158 97 115 16 68 72 258 27 64 95 182 224 259 14 168 54 110 48 153 21 62 144 243 63 247 78 116 186 261 33 223 100 262 184 223 15 131 20 88 57 204 45 158 41 255 91 160 187 205 54 140 65 262 38 263 42 64 39 177 205 212 155 242 197 246 37 90 32 64 63 230 14 213 127 145 91 127 69 77 8 154 23 250 142 152 76 199 74 211 29 210 66 68 29 233 107 202 55 121 155 158 30 93 175 219 13 209 84 230 124 136 149 259 82 258 78 84 71 117 32 84 129 255 144 183 173 248 49 …
Output: 2

Example 2:

Input: 777 951 1 777 209 630 32 207 205 666 237 388 490 604 3 354 68 211 436 558 492 566 485 731 94 637 344 694 75 429 372 452 141 567 62 450 279 720 323 433 127 746 629 741 464 511 185 605 18 42 45 187 103 739 266 274 117 734 391 431 354 382 184 342 46 551 603 775 344 578 65 287 269 387 16 337 46 588 234 494 230 767 3 179 291 547 298 545 496 723 218 568 110 719 155 294 487 528 147 490 213 532 448 597 520 548 440 719 617 734 266 681 546 634 457 483 236 376 537 594 411 497 75 229 18 82 435 525 269 758 466 546 416 724 521 524 358 702 292 331 63 562 390 758 440 765 71 577 545 667 543 559 70 598 650 766 285 594 643 664 346 701 163 219 60 234 476 681 193 514 151 193 551 696 178 726 96 592 3 144 294 642 586 647 168 495 77 777 515 697 94 148 440 747 98 613 86 556 473 774 403 429 250 419 135 449 133 242 …
Output: 11

Example 3:

Input: 334 1130 1 334 44 276 296 317 64 281 43 289 223 225 110 333 30 94 158 252 221 228 17 92 93 286 31 312 72 124 83 206 7 156 14 107 4 299 226 281 29 332 14 148 77 107 20 114 50 157 292 309 176 312 67 254 193 240 3 94 111 163 60 331 74 177 99 158 272 283 8 197 1 157 39 120 103 294 289 327 121 308 22 164 246 308 65 145 217 320 91 226 104 139 30 45 164 247 62 114 73 243 258 312 102 182 57 226 75 233 230 283 211 244 12 220 93 317 61 219 90 188 194 236 50 143 94 284 156 290 32 306 214 235 122 277 17 157 39 223 168 220 13 317 152 216 168 289 60 225 62 258 229 317 113 321 203 323 7 50 90 334 4 298 136 235 154 277 55 221 175 254 235 310 103 132 181 183 125 276 122 217 200 208 253 330 79 132 22 24 175 294 99 251 13 304 10 253 40 103 126 133 227 297 48 214 304 332 8 65 30 219 188 275 1 24 237 318 172 2…
Output: 4

Constraints:

1 <= n <= 948; 0 <= m <= 1896.

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