Graph Shortest Path Class
Programming Interview
Hard
4 views
Problem Description
Input provides {x}. Create Graph class with bfs(s,t) method. Output shortest distance 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))
class Graph:
def __init__(self,n):
self.n=n
self.g=[[] for _ in range(n+1)]
def add(self,u,v):
self.g[u].append(v)
self.g[v].append(u)
def bfs(self,s,t):
dist=[-1]*(self.n+1)
q=deque([s])
dist[s]=0
while q:
u=q.popleft()
if u==t:
return dist[u]
for v in self.g[u]:
if dist[v]==-1:
dist[v]=dist[u]+1
q.append(v)
return -1
G=Graph(n)
for _ in range(m):
u=int(next(it)); v=int(next(it))
G.add(u,v)
s=int(next(it)); t=int(next(it))
print(G.bfs(s,t))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!