Shortest Path BFS
Programming Interview
Hard
5 views
Problem Description
Input provides {x}. Implement bfs to output shortest distance (edges count) or -1.
Input Format
First line n m. Next m lines u v. Last line s t.
Output Format
One integer distance.
Sample Test Case
Input:
5 5
1 2
2 3
3 4
4 5
1 5
1 4
Official Solution
import sys
from collections import deque
p=sys.stdin.read().strip().split()
if not p: sys.exit(0)
it=iter(p)
n=int(next(it)); m=int(next(it))
g=[[] for _ in range(n+1)]
for _ in range(m):
u=int(next(it)); v=int(next(it))
g[u].append(v)
g[v].append(u)
s=int(next(it)); t=int(next(it))
def bfs(start,target):
dist=[-1]*(n+1)
q=deque([start])
dist[start]=0
while q:
u=q.popleft()
if u==target:
return dist[u]
du=dist[u]
for v in g[u]:
if dist[v]==-1:
dist[v]=du+1
q.append(v)
return -1
sys.stdout.write(str(bfs(s,t)))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!