-
Notifications
You must be signed in to change notification settings - Fork 0
/
11779.py
44 lines (40 loc) · 1.24 KB
/
11779.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
from heapq import heappush, heappop
def Dijkstra(graph, start, end, num_V):
visited = [False] * (num_V+1)
distance = [INF] * (num_V+1)
path={}
for i in range(1,num_V+1):
if graph[start][i]!=INF:
path[i]=start
else:
path[i]=None
distance[start], visited[start] = 0, True
heap=[(0,start)]
while visited[end] == False:
current_distance, current_node = heappop(heap)
visited[current_node] = True
for V, weight in enumerate(graph[current_node]):
if weight != INF and visited[V] == False:
D=weight+current_distance
if D<distance[V]:
distance[V]=D
path[V]=current_node
heappush(heap,(D,V))
print(distance[end])
pathlist=[]
while True:
pathlist.append(end)
if end==start:
break
end=path[end]
print(len(pathlist))
print(*pathlist[::-1])
V=int(input())
E=int(input())
INF=float('inf')
city=[[INF]*(V+1) for _ in range(V+1)]
for _ in range(E):
a,b,c=map(int,input().split())
city[a][b]=min(city[a][b],c)
start,end=map(int,input().split())
Dijkstra(city,start,end,V)