Shortest Path to Target Node
MediumPractice library · +20 XPgraphsbfsshortest path
You are given an undirected graph with N nodes, labeled 0 to N-1, and M edges. You are also given a starting node S and a target node T. Find the length of the shortest path between S and T. If no path exists, output -1. The graph is guaranteed to be connected.
Input
The first line contains three integers N, M, S, and T separated by spaces. The next M lines each contain two integers u and v, representing an undirected edge between node u and node v.
Output
Print a single integer: the length of the shortest path from S to T, or -1 if no path exists.
Constraints
1 <= N <= 200000, 0 <= M <= 200000, 0 <= S, T, u, v < N. S and T may be the same. The graph is connected.
Time limit 1 s (native code; slower languages get more)Memory 256 MB13 hidden tests
Example 1
Input
5 5 0 4 0 1 0 2 1 3 2 3 3 4
Output
3
Shortest path from 0 to 4 is 0 -> 2 -> 3 -> 4, length 3.
Example 2
Input
3 2 0 1 0 1 1 2
Output
1
Shortest path from 0 to 1 is 0 -> 1, length 1.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
5 5 0 4 0 1 0 2 1 3 2 3 3 4
Example 2 input
3 2 0 1 0 1 1 2