CT56020

Felix and the Northern routes

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Felix found an old ledger of routes in the apiary attic at the observatory of Starfall. 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 <= 1286; 0 <= m <= 2572.

Example 1:

Input: 508 507 1 508 188 466 179 190 440 448 297 484 205 311 318 507 30 356 118 216 128 504 135 139 193 371 145 386 198 379 58 113 275 475 178 217 171 493 372 377 324 443 139 390 460 486 181 261 3 180 55 237 40 455 50 240 315 500 333 492 45 51 316 384 1 191 417 425 105 302 55 250 170 493 5 288 322 380 68 415 215 393 75 403 244 353 193 273 251 296 437 493 206 270 15 254 27 499 131 289 365 371 39 162 79 276 11 438 65 312 70 247 423 457 43 191 274 428 94 505 133 261 214 448 173 396 294 496 327 497 262 447 244 453 20 110 63 67 325 478 3 508 360 424 139 154 375 407 19 480 75 105 263 301 40 496 31 161 282 415 84 92 109 449 42 439 14 503 88 95 128 428 9 278 18 313 313 367 233 414 222 307 110 217 126 299 384 412 111 165 254 278 64 455 226 501 21 122 198 323 345 462 116 503 238 449 304 482 12 152 142 394 …
Output: 15

Example 2:

Input: 762 761 1 762 155 738 114 282 287 370 293 377 37 586 54 322 693 744 93 680 21 32 434 628 284 502 291 600 13 241 424 639 47 201 445 562 483 571 138 493 13 756 137 652 211 649 306 570 322 452 178 751 66 110 189 458 104 408 331 401 186 452 101 481 345 722 224 287 38 236 54 533 70 406 405 715 350 446 590 621 408 447 204 429 292 448 142 735 212 547 609 646 24 140 50 362 189 315 380 515 221 610 79 482 68 182 79 443 744 754 214 252 239 592 56 729 687 744 211 302 114 203 521 555 31 321 35 687 452 514 593 631 169 627 403 743 311 683 580 744 498 758 160 615 97 289 170 298 277 709 91 663 349 544 195 624 124 724 16 395 116 294 510 512 22 344 279 681 123 251 303 690 258 333 179 299 72 440 225 248 579 662 43 726 219 742 416 447 128 747 29 738 576 738 137 677 595 733 245 375 82 317 102 612 138 239 376 42…
Output: 15

Example 3:

Input: 1254 1253 1 1254 509 1149 174 946 256 1105 361 372 70 285 743 984 198 1105 64 358 739 1066 515 1078 518 914 116 1165 410 765 144 1011 256 387 41 245 106 176 348 633 186 315 240 792 459 1002 71 874 232 564 3 1029 276 1170 294 304 641 1053 243 257 769 845 730 1221 808 1033 11 1160 1192 1245 290 343 454 954 262 280 289 291 498 1049 665 685 349 1090 1067 1092 966 1014 1055 1235 7 931 65 779 27 158 177 965 627 1103 889 917 197 1166 642 1077 255 981 948 1112 852 918 425 1243 843 884 743 1021 75 985 589 832 615 1002 271 972 305 515 169 363 1128 1154 365 1035 597 811 958 1200 10 1161 79 1245 663 666 12 125 485 687 358 873 563 1004 244 433 198 404 2 1169 331 593 499 1000 153 1071 475 1163 97 923 163 235 460 564 538 855 713 746 414 494 3 391 292 438 225 443 492 1057 298 1051 11 286 247 1213 347 953 …
Output: 14

Constraints:

1 <= n <= 1286; 0 <= m <= 2572.

Loading...
Test Cases:No test cases
No test cases available.
Felix and the Northern routes - MEDIUM Coding Problem | CodeTikki