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

문제

무방향 그래프가 존재할 때 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 이때 반드시 두 개의 정점을 통과하여 N까지 이동하는 최소 경로를 구하라.

 

입력

첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존재하며, 그 거리가 c라는 뜻이다. (1 ≤ c ≤ 1,000) 다음 줄에는 반드시 거쳐야 하는 두 개의 서로 다른 정점 번호 v1과 v2가 주어진다. (v1 ≠ v2, v1 ≠ N, v2 ≠ 1)

 

출력

첫째 줄에 두 개의 정점을 지나는 최단 경로의 길이를 출력한다. 그러한 경로가 없을 때에는 -1을 출력한다.

---

접근

최단경로를 구하기위해 다익스트라 알고리즘으로 접근을 하였다.

이때 반드시 지나가야하는 두 개의 정점을 V1, V2라고 했을 때 1->V1의 최단경로, V1->V2의 최단경로, V2->N의 최단경로의 합을 구한다. 또한 반대로 1->V2, V2->V1, V1->N의 경로도 구하여 둘 중 최솟값을 구한다.

 

구현

- 도착지 N을 입력받고 그래프에 대한 정보를 저장한다.

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

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

V1, V2 = map(int, input().split())

 

- 다익스트라 알고리즘을 통해 출발지와 도착지의 최단경로를 반환하는 함수를 만들었다.

- (여기서 처음 dist[start]에 0을 대입안해주었는데 83%에서 계속 틀리다고 나왔다.) v1이 1이 될 수 있나?

def dijkstra(start, end):
    dist = [INF] * (N+1)
    hq = []
    heapq.heappush(hq, (0, start))
    dist[start] = 0
    while hq:
        cur_weight, cur_node = heapq.heappop(hq)

        if dist[cur_node] < cur_weight:
            continue

        for next_node, weight in graph[cur_node]:
            weight += cur_weight
            if dist[next_node] > weight:
                dist[next_node] = weight
                heapq.heappush(hq, (weight, next_node))

    return dist[end]

 

- 이제 두 개의 경로에 대해 최소경로를 찾고

- 위에서 구한 두 개의 값을 비교하여 최솟값을 result에 저장한다.

- 만약 result가 INF 이상이라면 경로를 찾을 수 없다는 것이기 때문에 -1을 출력하고 그렇지않으면 result를 그대로 출력한다.

# 1->V1->V2->N
answer1 = dijkstra(1, V1) + dijkstra(V1, V2) + dijkstra(V2, N)
# 1->V2->V1->N
answer2 = dijkstra(1, V2) + dijkstra(V2, V1) + dijkstra(V1, N)

result = min(answer1, answer2)
print(result if result < INF else -1)

---

전체 코드

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

def dijkstra(start, end):
    dist = [INF] * (N+1)
    hq = []
    heapq.heappush(hq, (0, start))
    dist[start] = 0
    while hq:
        cur_weight, cur_node = heapq.heappop(hq)

        if dist[cur_node] < cur_weight:
            continue

        for next_node, weight in graph[cur_node]:
            weight += cur_weight
            if dist[next_node] > weight:
                dist[next_node] = weight
                heapq.heappush(hq, (weight, next_node))

    return dist[end]

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

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

V1, V2 = map(int, input().split())

# 1->V1->V2->N
answer1 = dijkstra(1, V1) + dijkstra(V1, V2) + dijkstra(V2, N)
# 1->V2->V1->N
answer2 = dijkstra(1, V2) + dijkstra(V2, V1) + dijkstra(V1, N)

result = min(answer1, answer2)
print(result if result < INF else -1)