Submission #2556407

---

Source Code Expand

from heapq import heappop,heappush
def dijkstra(n,s,adj):
	dis = [float("inf") for i in range(n+1)]
	dis[s],q = 0,[[0,s]]
	while q:
		num2,num = heappop(q)
		for i,j in adj[num]:
			if dis[i]>num2+j:
				dis[i] = num2+j
				heappush(q,[dis[i],i])
	return dis
n,m = (int(i) for i in input().split())
s,t = (int(i) for i in input().split())
x = [[int(i) for i in input().split()] for i in range(m)]
road,flag = [[] for i in range(n+1)],False
for i,j,k in x:
	road[i].append([j,k])
	road[j].append([i,k])
sl,tl = dijkstra(n,s,road),dijkstra(n,t,road)
for i in range(1,n+1):
	if sl[i]==tl[i] and sl[i]!=float("inf"):
		flag = True
		break
if flag: print(i)
else: print(-1)

Submission Info

Judge Result