CT31753

Prismatic corridors Fewest Hops

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

In the shale slopes of Greystone, Lothar the paymaster keeps careful count of the corridors. Prepare the winter inventory, every figure matters. 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 <= 1871; 0 <= m <= 3742.

Example 1:

Input: 1333 1332 1 1333 289 376 228 1053 147 938 852 978 508 783 178 1150 16 409 381 1056 220 626 890 925 91 575 434 1055 216 1253 116 1085 197 1237 938 939 396 827 527 1320 229 389 1094 1226 289 813 928 1328 194 1273 1177 1304 272 608 1061 1155 789 1249 241 470 397 1173 234 861 357 441 98 1094 49 57 511 1071 320 484 435 1106 353 448 430 657 802 944 304 1202 1021 1201 413 1288 16 917 297 862 799 1315 48 134 858 884 770 915 981 1166 279 1264 326 447 696 1039 199 934 165 309 280 289 95 882 458 489 137 1287 38 275 328 928 279 486 127 429 316 542 427 913 1 949 452 1318 595 1146 435 738 457 551 94 507 561 780 776 1253 329 820 721 762 1232 1289 554 986 38 1203 73 1032 192 1029 81 763 506 1168 711 831 587 1283 565 1216 1179 1233 238 975 213 225 413 486 192 1045 90 1040 118 647 1000 1103 215 391 104 1055…
Output: 9

Example 2:

Input: 503 2141 1 503 250 410 79 445 166 202 29 486 65 295 415 436 361 398 168 391 176 258 337 450 58 171 388 437 176 276 226 360 139 433 22 225 45 274 355 416 128 347 42 149 222 449 499 503 423 481 316 352 186 325 235 422 364 436 104 221 104 257 147 413 7 10 26 244 85 403 193 402 297 443 210 389 151 315 265 368 211 473 138 475 87 452 47 134 1 477 15 148 96 152 15 327 232 318 268 361 163 339 220 299 90 129 13 285 431 477 241 398 68 311 446 459 70 248 105 229 163 269 23 101 126 442 189 383 162 467 295 315 150 345 51 136 182 223 38 406 74 229 343 490 63 171 64 398 43 395 189 266 357 448 285 315 178 190 11 56 164 336 184 409 170 344 107 222 1 127 59 362 315 362 396 477 147 428 291 309 113 161 109 278 258 309 288 419 215 220 401 470 400 427 320 396 136 501 215 438 350 452 158 414 155 338 23 100 67 23…
Output: 3

Example 3:

Input: 1010 2112 1 1010 57 183 172 846 488 756 731 926 270 537 291 990 410 967 345 640 342 370 606 810 605 953 356 424 163 366 292 338 415 777 55 461 370 556 401 906 438 465 227 371 50 517 228 949 272 696 635 889 488 924 157 284 639 822 201 790 457 985 528 543 426 821 55 511 68 74 724 868 58 619 967 981 247 985 271 562 341 678 358 380 65 397 25 438 171 241 68 974 449 648 164 705 193 475 45 577 560 864 811 946 3 144 555 669 186 951 327 979 168 341 282 495 547 552 32 59 510 534 58 976 1 684 205 285 92 863 161 292 363 506 376 589 61 305 283 917 612 762 364 722 389 1005 521 725 585 612 225 286 2 110 3 260 184 295 85 593 46 834 52 752 565 1010 110 409 314 416 617 818 520 783 619 817 77 268 364 650 397 632 534 750 896 899 681 893 577 839 445 833 150 803 882 990 149 611 377 530 220 350 162 753 758 1007 …
Output: 4

Constraints:

1 <= n <= 1871; 0 <= m <= 3742.

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