[Baekjoon 1504] 특정한 최단 경로

문제

💛Ⅳ [Baekjoon 1504 - 특정한 최단 경로]

문제 풀이 방법

1번 지점에서 N번 지점까지 이동하는 간선이므로 다익스트라 알고리즘 문제이다. 하지만 2 정점을 거쳐서 가야하므로 다익스트라 알고리즘을 여러 번 사용해야 한다.

1. 1 → v1 → v2 → N 일 때의 최단거리와 1 → v2 → v1 → N 일 때의 최단거리를 구하여 최솟값을 찾는다.

2. 1번을 시작노드로 하여 다익스트라 알고리즘 수행

   1 - v1까지의 최단거리와, 1 - v2까지의 최단거리를 구한다.

3. v1, v2를 시작노드로 하여 다익스트라 알고리즘 수행

   v1 - v2, v1 - N까지의 최단거리와, v2 - v1, v2 - N까지의 최단거리를 구한다.

풀이 코드

Python

def dijkstra(start):
    q = []
    distance = [INF] * (N + 1)
    heapq.heappush(q,(0,start))
    distance[start] = 0
    while q:
        dist, node = heapq.heappop(q)
        if distance[node] < dist: # 이미 처리한 적 있는 노드라면 무시
            continue
        for i in graph[node]: # 현재 노드와 연결된 노드들 확인
            cost = dist+i[1] # 거리 계산
            if cost < distance[i[0]]: # 현재 최단거리보다 작다면 갱신하고 힙에 push
                distance[i[0]] = cost
                heapq.heappush(q,(cost, i[0]))
    return distance

import sys, heapq
input = sys.stdin.readline

INF = int(1e7)
N, E = map(int, input().split())
graph = [[] for _ in range(N+1)]

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

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

shortest_dist = dijkstra(1)
distance_v1 = shortest_dist[v1]
distance_v2 = shortest_dist[v2]

shortest_dist = dijkstra(v1)
distance_v1 += shortest_dist[v2]
distance_v2 += shortest_dist[N]

shortest_dist = dijkstra(v2)
distance_v2 += shortest_dist[v1]
distance_v1 += shortest_dist[N]

answer = min(distance_v1,distance_v2)
if answer >= INF:
    print(-1)
else:
    print(answer)