Submission #1553149

---

Source Code Expand

import heapq
n,m = map(int,input().split())
s,t = map(int,input().split())
INF = 1000000000
d = [[INF if i != j else 0 for i in range(n)] for j in range(n)]
for i in range(m):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = min(d[x-1][y-1],z)
    d[y-1][x-1] = min(d[x-1][y-1],z)
 
dist_s = [INF for i in range(n)]
dist_t = [INF for i in range(n)]
 
search = []
heapq.heappush(search,(0, s-1))
while len(search) > 0:
    dist,node = heapq.heappop(search)
    if dist_s[node] < dist:
        continue
    dist_s[node] = dist
    for i in range(n):
        if i != node and dist + d[node][i] < dist_s[i]:
            dist_s[i] = dist + d[node][i]
            heapq.heappush(search,(dist+d[node][i], i))
 
search = []
heapq.heappush(search,(0, t-1))
while len(search) > 0:
    dist,node = heapq.heappop(search)
    if dist_t[node] < dist:
        continue
    dist_t[node] = dist
    for i in range(n):
        if i != node and dist + d[node][i] < dist_t[i]:
            dist_t[i] = dist + d[node][i]
            heapq.heappush(search,(dist+d[node][i], i))
if s != t:           
    ans = -1
else:
    ans = 0
for i in range(n):
    if dist_s[i] == dist_t[i] and dist_s < INF:
        ans = i+1
print(ans)

Submission Info

Judge Result