1238백준

Dijkstra

 
from sys import stdin
 
N,M,X = map(int, stdin.readline().split(" "))
INF = int(1e9)
graph = {n : [] for n in range(N+1)}
rgraph = {n : [] for n in range(N+1)}
 
for _ in range(M):
  s,e,c = map(int, stdin.readline().split(" "))
  graph[s].append([e,c])
  rgraph[e].append([s,c])
 
 
 
def nearShort(dist,visit):
  global N
  retv =-1
  d = INF
  for i in range(1,N+1):
    if d> dist[i] and  visit[i] == False:
      d = dist[i]
      retv = i
  return retv
 
def shortcut(x,G):
  global N
  visit = [False for i in range(N+1)]
  dist = [INF for i in range(N+1)]
 
  visit[x] = True
  dist[x] = 0
  
  for g in G[x]:
    dist[g[0]] = g[1]
  
  for i in range(N-1):
    nextx = nearShort(dist,visit)
    visit[nextx] = True
    for ng in G[nextx]:
      if dist[nextx] + ng[1] < dist[ng[0]]:
        dist[ng[0]] = dist[nextx] + ng[1]
 
  return dist
 
# print(shortcut(X,graph))
# print(shortcut(X,rgraph))
 
ans = [x+y for x,y in zip(shortcut(X,graph)[1:],shortcut(X,rgraph)[1:])]
print(max(ans))