CT31386

Tomas's Ledger of roads

MediumL4 · Loop LordAcceptance: 0.0%XP: 35

The harbor bell rings at the railway depot of Cinderline; Tomas weighs the day's roads manifests and starts the calculations. 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 <= 1690; 0 <= m <= 3380.

Example 1:

Input: 1218 1972 1 1218 372 795 451 1025 356 876 799 956 902 1026 145 239 44 1114 428 646 625 655 75 963 820 1178 753 918 307 524 547 814 400 920 125 764 24 846 431 527 94 1141 533 599 731 1069 642 837 549 1185 1105 1161 388 1184 303 700 138 395 11 1032 75 720 386 613 208 1179 625 887 162 1139 6 160 140 505 637 1174 351 493 528 864 196 973 495 914 94 309 472 703 691 853 39 1031 339 794 521 643 783 1084 758 946 253 987 515 1139 528 624 739 1056 564 986 382 846 441 946 433 676 123 638 580 664 23 469 218 564 516 910 566 728 273 1187 876 896 457 768 17 1078 641 976 551 1007 171 921 163 1107 1083 1133 103 402 270 392 118 913 23 785 289 670 106 571 219 321 606 815 217 1143 459 1203 586 764 519 955 487 1031 86 137 201 773 309 663 186 1184 481 1053 199 475 429 1153 314 1048 427 450 659 861 155 953 116 67…
Output: 5

Example 2:

Input: 1031 1736 1 1031 436 722 636 842 459 549 98 436 307 956 892 908 435 844 292 646 423 756 617 767 807 988 598 815 104 628 557 600 167 977 455 905 387 906 204 927 587 687 950 955 587 618 946 974 147 649 143 778 235 506 462 658 158 394 932 946 290 688 310 1005 543 860 497 655 466 721 930 949 207 937 237 248 611 1022 356 574 526 1030 226 293 609 904 129 349 208 665 203 563 19 503 864 922 180 284 36 334 399 679 558 675 317 1009 207 928 250 359 321 679 23 505 302 386 611 630 690 1010 54 305 299 616 81 136 431 464 511 842 7 699 398 671 605 986 1027 1029 125 133 503 526 260 887 68 536 184 444 492 574 476 645 835 876 381 909 599 831 436 713 142 590 75 818 349 447 140 312 130 391 260 867 166 838 75 973 246 802 139 336 218 590 80 519 67 165 215 518 233 649 315 725 249 808 549 969 156 221 631 1012 355 …
Output: 7

Example 3:

Input: 692 1797 1 692 76 379 6 358 425 429 320 333 48 346 587 595 112 382 113 641 444 633 175 534 282 443 298 582 398 445 222 288 210 573 16 321 164 579 62 428 182 670 658 661 257 566 66 262 123 619 139 588 93 390 63 372 39 56 114 527 658 673 81 272 74 330 393 416 233 509 249 323 120 182 309 358 70 170 388 470 104 307 27 493 191 594 199 447 11 609 524 539 62 459 62 476 23 477 70 313 64 446 169 318 505 614 1 79 377 429 337 494 106 240 324 545 2 253 294 484 375 489 138 533 187 230 319 588 308 344 197 331 226 527 511 631 294 564 148 325 101 300 389 473 231 359 25 474 109 425 143 431 189 447 448 662 60 297 71 228 64 612 120 495 270 587 221 504 79 536 265 630 301 499 358 478 130 557 3 279 250 478 320 677 99 253 636 654 313 541 3 545 533 684 335 401 426 663 270 578 326 431 35 428 238 302 99 229 44 289 …
Output: 4

Constraints:

1 <= n <= 1690; 0 <= m <= 3380.

Loading...
Test Cases:No test cases
No test cases available.
Tomas's Ledger of roads - MEDIUM Coding Problem | CodeTikki