Dijkstra Shortest Path (Many Cases)
Programming Interview
Hard
5 views
Problem Description
For each testcase you get weighted undirected graph. Output shortest distance from 1 to n. If unreachable output -1.
Input Format
First integer t. For each: n m then m lines u v w.
Output Format
t lines distances.
Sample Test Case
Input:
1
5 6
1 2 2
1 3 4
2 3 1
2 4 7
3 5 3
4 5 1
Constraints
Sum of n+m over all testcases
Official Solution
import sys,heapq
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
out=[]
INF=10**30
for _ in range(t):
n=int(next(it)); m=int(next(it))
g=[[] for _ in range(n+1)]
for i in range(m):
u=int(next(it)); v=int(next(it)); w=int(next(it))
g[u].append((v,w))
g[v].append((u,w))
dist=[INF]*(n+1)
dist[1]=0
pq=[(0,1)]
while pq:
d,u=heapq.heappop(pq)
if d!=dist[u]:
continue
if u==n:
break
for v,w in g[u]:
nd=d+w
if nd<dist[v]:
dist[v]=nd
heapq.heappush(pq,(nd,v))
out.append(str(dist[n] if dist[n]<INF else -1))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!