[BOJ] 1504. 특정한 최단 경로

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

1504번: 특정한 최단 경로

 

 

1. 해결방법

"""
1. 아이디어
- 한 점에서 다른 점까지의 최소 비용 : 다익스트라
- 간선, 인접리스트 저장
- 거리 배열을 INF로 저장
- 조건이 n1, n2를 무조건 지나야 하기 때문에 두 가지 방법으로 나눈다
    - 1 -> n1 -> n2 -> n
    - 1 -> n2 -> n1 -> n
- heap이 빌때까지 다음을 반복
    - heap에서 최솟값을 꺼내고 최신값인지 비교
    - 인접리스트의 해당 노드를 가져와서 heap에 push

2. 시간복잡도
- O(ElogV)

3. 자료구조
- heap : [비용, 노드 번호]
- 인접리스트 : [비용, 노드 번호]
- 거리 배열 : [INF]
"""

 

 

2. 정답코드

import sys
import heapq
input = sys.stdin.readline
INF = sys.maxsize

N, M = map(int, input().split())

edge = [[] for _ in range(N + 1)]
for i in range(M):
    a, b, c = map(int, input().split())
    edge[a].append([c, b])
    edge[b].append([c, a])

include_node1, include_node2 = map(int, input().split())


def q(start):
    dist = [INF] * (N + 1)
    dist[start] = 0
    dist[1] = 0
    heap = [[dist[start], start]]

    while heap:
        ew, ev = heapq.heappop(heap)
        if dist[ev] != ew: continue
        for nw, nv in edge[ev]:
            if dist[nv] > ew + nw:
                dist[nv] = ew + nw
                heapq.heappush(heap, [dist[nv], nv])

    return dist

origin_dist = q(1)
node1_dist = q(include_node1)
node2_dist = q(include_node2)

# print('path1 ', origin_dist, node1_dist, node2_dist)
# print('path2 ', origin_dist, node2_dist, node1_dist)

path1 = origin_dist[include_node1] + node1_dist[include_node2] + node2_dist[N]
path2 = origin_dist[include_node2] + node2_dist[include_node1] + node1_dist[N]

result = min(path1, path2)
print(result if result < INF else -1)

기본 다익스트라 코드에서 크게 변형시키지 않은 문제였다.
하지만 조건 하나가 거슬렸는데, 특정한 노드를 무조건 방문해야한다는 점인데... 해결 방법은 두 가지가 있다.

1 -> n1 -> n2 -> n or 1 -> n2 -> n1 -> n 의 방법이다.
그래서 다익스트라 기본 코드를 함수로 두어서 시작점을 1과 특정한 두 노드로 두어서 나온 값의 거리 비용인 해당 인덱스의 값을 꺼내서 더하였다.

그리고 주의해야될 점은 양방향 이동이 가능하는 점 때문에 인접리스트 edge[]에 [a]와 [b] 둘다 append 해주어야 한다.

위 두가지 때문에 좀 헤맸다..