[baekjoon] 백준 1504번 : 특정한 최단 경로 (by python 파이썬) 다익스트라 최단경로 dijkstra

https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

정답 code

#특정한 최단 경로
import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

def dijkstra(start):
    visit = [INF]*(n+1)
    q = []
    heapq.heappush(q,(0,start))
    visit[start] = 0
    while q:
        dis, node = heapq.heappop(q)
        if visit[node]>= dis:
            for node_index, node_time in graph[node]:
                time = node_time + dis
                if visit[node_index]> time:
                    visit[node_index] = time
                    heapq.heappush(q,(time,node_index))
    return visit


n,m = map(int,input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    a,b,c = map(int,input().split())
    graph[a].append((b,c))
    graph[b].append((a,c))

v1,v2 = map(int,input().split())

one = dijkstra(1)
v1_ = dijkstra(v1)
v2_ = dijkstra(v2)

# 1번에서 v1, v2를 거쳐 n으로 가는경우, 1번에서 v2, v1을 거쳐 n으로 가는경우
total = min(one[v1]+v1_[v2]+v2_[n], one[v2]+v2_[v1]+v1_[n])

print(total if total < INF else -1)

 

solution

앞서 풀었던 1238번과 거의 유사한 문제라 다익스트라를 이용해 쉽게 해결 할 수 있었다.

다만 신경 써야되는 부분은 v1과 v2를 거쳐 가야됨으로 다익스트라를 이용해 v1 과 v2의 최단 거리들도 구해서 해결해야 한다.

 

1번에서 n으로 주어진 v1,v2를 거쳐가는 경우는 두가지다.

1. 1번에서 v1,v2순으로 방문한다음 n 방문

2. 1번에서 v2,v1순으로 방문한다음 n 방문

이 둘중 최솟 값을 출력해주면 된다.