1504 백준 파이썬

다익스트라 알고리즘에 대한 정확한 이해가 없어서 어려웠던 문제. 이 문제를 통해서 개념을 확실히 익혔다.

 

다익스트라는 dfs와 비슷한 방식으로 작동한다.

최단 경로는 최단 경로의 합이라는 알고리즘으로 작동한다. 따라서 힙을 통해 구현할 수 있다.

약간 조건이 잔뜩붙은 dfs같은 느낌이다.

 

시작점에서 최단경로를 찾는다 -> 최단경로를 힙에 넣는다 -> 최단경로를 꺼내어 시작점과 중간 경로까지의 값과 비교한 후에 최단 경로가 더 짧은 경우에만 더 진행한다.(이걸로 시간초과가 갈린다.) -> 현재 저장된 중간경로에서 또 다른 경유 지점까지의 합이 저장된 거리보다 짧을 경우, 저장된 거리를 갱신한다.  -> 저장된 거리를 힙에 다시 넣는다.

 

그리고 이 문제의 경우, 특정한 경로를 지나야 하는데 그 발상을 떠올리지 못하면 풀지 못하는 문제다.

다만 발상의 전제가 다익스트라 알고리즘과 같은 맥락이므로, 결국은 고난이도 다익스트라 정도라고 할 수 있겠다.

 

v1,v2를 반드시 거치는 경로는

1->v1->v2->n 

또는

1->v2->v1->n

두가지로 한정된다.

따라서 이 두 가지 값 중 작은 값을 출력하면 된다.

 

import sys
import heapq
input=sys.stdin.readline
n,e=map(int,input().split())
INF=int(1e9)
l=[[INF for _ in range(n+1)] for _ in range(n+1)]
v=[[] for _ in range(n+1)]
for _ in range(e):
    a,b,c=map(int,input().split())
    l[a][b]=c
    l[b][a]=c
    l[a][a]=0
    l[b][b]=0
v1,v2=map(int,input().split())

def dik(start,fin):
    distance=[INF]*(n+1)
    d = []
    heapq.heappush(d,(0,start))
    distance[start]=0
    while d:
        dist,t=heapq.heappop(d)
        if distance[t]<dist:
            continue
        for q in range(1,n+1):
            if dist+l[t][q]<distance[q]:
                distance[q]=dist+l[t][q]
                heapq.heappush(d,(distance[q],q))
    return distance[fin]
res=min(dik(1,v1)+dik(v1,v2)+dik(v2,n),dik(1,v2)+dik(v2,v1)+dik(v1,n))
if res<INF:
    print(res)
else:
    print(-1)