1238 백준 파이썬

별거 없는 다익스트라 문제.

하는김에 다익스트라를 복습해 보자.

 

다익스트라는 시작점으로부터 어떤 도착점 까지의 최단 거리를 구하는 알고리즘이다.

 

그래서 g라는 리스트에 가는데 걸리는 (시간,목적지)를 저장한다.

그리고 다익스트라 함수안에서 distance라는 리스트를 만든다. 여기에다가 최단 거리를 갱신해 줄 것이다. 최단거리를 갱신해야 하므로 int(1e9)로 선언한다.

 

그 후에 힙을 만들어서 cost와 start를 넣어준다.

그리고 힙에 저장된 것이 없을 때 까지 cost, now를 꺼내어서 비교한다. 이때, 저장된 cost가 distance[now]보다 크면 더이상 볼 필요가 없으므로 넘어간다.

 

그렇지 않다면, g[now]에 있는 리스트들을 반복시킨다.

g[now]는 cost와 목적지로 저장되어 있기 때문에 cost+distance[now]가 distance[목적지]보다 작아야지만 heap안에 넣는다. (heap을 사용했기때문에 최소비용순으로 입력된다.)

 

import heapq
n,m,x=map(int,input().split())
INF=int(1e9)
g=[[] for x in range(n+1)]
for _ in range(m):
    a,b,t=map(int,input().split())
    g[a].append((t,b))

def dik(start,end):
    distance=[INF for x in range(n+1)]
    distance[start]=0
    heap=[(0,start)]
    while heap:
        cost,now=heapq.heappop(heap)
        if distance[now]<cost:
            continue
        for x in g[now]:
            tmp=x[0]+cost
            if tmp<distance[x[1]]:
                distance[x[1]]=tmp
                heapq.heappush(heap,(tmp,x[1]))
    return distance[end]
res=[0 for x in range(n+1)]
for t in range(1,n+1):
    res[t]+=dik(t,x)+dik(x,t)
print(max(res[1:]))