[BOJ/백준] 1504 특정한 최단 경로

import sys
import heapq
def distra(start,ind):
    distance[ind][start] = 0
    node_list = []
    heapq.heappush(node_list,(0,start))
    while node_list:
        dis,node = heapq.heappop(node_list)
        if dis > distance[ind][node]:
            continue
        for next_node in graph[node]:
            if distance[ind][next_node] > dis + graph[node][next_node]:
                distance[ind][next_node] = dis + graph[node][next_node]
                heapq.heappush(node_list,(distance[ind][next_node],next_node))
input = sys.stdin.readline

N, E = map(int,input().split())
graph = [{} for i in range(N+1)]

for _ in range(E):
    A,B,C = map(int,input().split())
    graph[A][B] = C
    graph[B][A] = C

ess = list(map(int,input().split()))

INF = float('inf')
distance = [[INF]*(N+1) for _ in range(3)]

distra(1,0)
distra(N,1)
distra(ess[0],2)

a = distance[0][ess[0]] + distance[1][ess[1]] + distance[2][ess[1]]

b = distance[0][ess[1]] + distance[1][ess[0]] + distance[2][ess[1]]
result = min(a,b)
if result == INF:
    print(-1)
else:
    print(result)

 

이 문제는 다익스트라를 이용해서 푸는 문제이다. 대신 입력으로 주어진 두 정점을 무조건 통과 해야하는 문제였다.

 

그렇기 때문에 두가지 경로로 가능하다고 생각했다.

시작점 : 1번노드 /  도착점 : N번노드 경유노드 : A,B번 노드

라고 하겠다.

 

1번노드 ->A번노드 -> B번노드 -> N번노드

1번노드 ->B번노드 -> A번노드 -> N번노드

 

라고 생각했다.

 

이 두 가지 경로에 대해서 구하고, 둘중의 최저값이 정답이 된다.

 

이걸 한번에 구하기 위해, 총 3번의 다익스트라를 해주었다.

distance라는 2차원 배열을 만들어두고, 열은 전체 distance를 넣어주는 역할을 하고,

0번 행은 1번노드에서의 다익스트라

1번 행은 N번 노드에서의 다익스트라

2번 행은 A번 노드에서의 다익스트라

가 저장되게 해놓았다.

 

그래서 각각의 경로에 맞게 더해주기만 하면 되고,

 

만약 최저값이 INF로 나올시, A,B번 노드를 동시에 통과하는 경우는 없는 것이므로, -1을 출력하도록 했다.