백준 1504 특정한 최단경로 문제 풀이

백준 1504 - 특정한 최단경로

문제

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

방향이 없는 양의 정수의 거리로 이루어진 그래프가 주어진다. 1번부터 n번까지. 1->n 번 노드까지 가는 최단경로를 구하는 문제. 단, 특정 노드들을 꼭 거쳐 가야한다. v1,v2 두개의 노드를 거쳐 n까지 가는 최단 경로를 구한다.

가능한 경로 경우의 수는 2가지

1. 1 -> v1 -> v2 -> n
2. 1 -> v2 -> v1 -> n

1번과 2번 경로의 거리 중 짧은 것이 답이다.

• 다익스트라 알고리즘
  • 시작점에서 다른 모든 점까지의 최단 거리를 구하는 알고리즘. N*N

위의 경우에서 시작점이 될 수 있는 경우는 1, v1, v2 이 3점이다. 다익스트라 알고리즘을 돌려 3개의 리스트를 반환받는다. 각 리스트는 각 시작점부터 다른 모든 점까지의 최단 거리가 갱신되어 있는 리스트이다. 3개의 리스트를 가지고 최단 거리를 구한다.

만약 3과7을 거쳐서 9번까지 가는 최단 경로를 구하는 경우

• dijkstra(1) -> a
• dijkstra(3) -> b
• dijkstra(7) -> c

다익스트라를 세번 돌려서 최단 거리가 저장된 리스트를 얻는다.

a[3] = 1 -> 3까지의 최단 거리 b[7] = 3 -> 7까지의 최단 거리 c[9] = 7 -> 9까지의 최단 거리

이렇게 총 3개의 구간을 모두 더한다. v1, v2의 순서를 바꾸어 나머지 경로 경우의 수를 구하고 이 두 개 중에 더 작은 것이 정답이다.

코드

import heapq
import sys
input = sys.stdin.readline
n, e = map(int, input().split())
graph = [ [0]*(n+1) for _ in range(n+1)]
for _ in range(e):
    s, t, d = map(int, input().split())
    graph[s][t] = d
    graph[t][s] = d

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

def dijkstra(start,graph):
    distance = [sys.maxsize] * (n+1)
    distance[start] = 0 
    que = []
    heapq.heappush(que, (distance[start], start))
    
    while que:
        dist, now = heapq.heappop(que)
        if distance[now] < dist:continue
        
        for i in range(1, n+1):
            if graph[now][i] == 0 or i == now:continue
            dd = dist + graph[now][i]
            if dd < distance[i]:
                distance[i] = dd 
                heapq.heappush(que, (dd, i))
    
    return distance


path = []
for start in [1, v1, v2]:
    path.append(dijkstra(start, graph))
    
answer = min(path[0][v1] + path[1][v2] + path[2][n], path[0][v2] + path[2][v1] + path[1][n])

    
print(answer if answer < sys.maxsize else -1)