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
45
|
# Uses python3
import sys
import heapq
def distance(adj, cost, s, t):
if s == t:
return 0
dist = [float('inf')] * len(adj)
visited = [False] * len(adj)
dist[s] = 0
q = []
heapq.heappush(q, (dist[s], s))
while len(q) != 0:
u = heapq.heappop(q)[1]
if visited[u]:
continue
visited[u] = True
if len(adj[u]) > 0:
for i in range(len(adj[u])):
if dist[adj[u][i]] > dist[u] + cost[u][i]:
dist[adj[u][i]] = dist[u] + cost[u][i]
heapq.heappush(q, (dist[adj[u][i]], adj[u][i]))
if dist[t] == float('inf'):
return -1
return dist[t]
if __name__ == '__main__':
input = sys.stdin.read()
data = list(map(int, input.split()))
n, m = data[0:2]
data = data[2:]
edges = list(zip(zip(data[0:(3 * m):3], data[1:(3 * m):3]), data[2:(3 * m):3]))
data = data[3 * m:]
adj = [[] for _ in range(n)]
cost = [[] for _ in range(n)]
for ((a, b), w) in edges:
adj[a - 1].append(b - 1)
cost[a - 1].append(w)
s, t = data[0] - 1, data[1] - 1
print(distance(adj, cost, s, t))
|
