41 lines
No EOL
887 B
Python
41 lines
No EOL
887 B
Python
n, m, s, t = map(int, input().split())
|
|
|
|
graph = [[] for _ in range(n + 1)]
|
|
in_degree = [0] * (n + 1)
|
|
|
|
for _ in range(m):
|
|
u, v, weight = map(int, input().split())
|
|
graph[u].append((v, weight))
|
|
in_degree[v] += 1
|
|
|
|
queue = []
|
|
for i in range(1, n + 1):
|
|
if in_degree[i] == 0:
|
|
queue.append(i)
|
|
|
|
order = []
|
|
head = 0
|
|
|
|
while head < len(queue):
|
|
current = queue[head]
|
|
head += 1
|
|
order.append(current)
|
|
|
|
for neighbor, weight in graph[current]:
|
|
in_degree[neighbor] -= 1
|
|
if in_degree[neighbor] == 0:
|
|
queue.append(neighbor)
|
|
|
|
dist = [10**18] * (n + 1)
|
|
dist[s] = 0
|
|
|
|
for node in order:
|
|
if dist[node] != 10**18:
|
|
for neighbor, weight in graph[node]:
|
|
if dist[node] + weight < dist[neighbor]:
|
|
dist[neighbor] = dist[node] + weight
|
|
|
|
if dist[t] == 10**18:
|
|
print("Unreachable")
|
|
else:
|
|
print(dist[t]) |