[Python 3] BOJ - 1504 "특정한 최단 거리"

 # 문제 링크 : https://www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

 

 # 풀이 :

개인적으로 문제의 핵심은 출발점이 정해져 있다는 것이다. 따라서 반드시 거쳐야 하는 두 점을 x, y라고 한다면 경우를 나눠 볼 수 있다. 

 1. 정점 1 → 정점 x → 정점 y → 정점 N

 2. 정점 1 → 정점 y → 정점 x → 정점 N

가능한 두 가지 경로 중 더 짧은 거리가 문제에서 요구하는 답이므로 경로 1과 경로 2의 리턴값을 비교해주면 된다. 만일 정점 1과 2 모두 INF값을 가진다면 어떠한 경우에도 1번 정점에서 출발하여 x, y를 거쳐 N번 정점으로 갈 수 없다는 뜻이므로 -1을 출력한다. 또한 다익스트라 알고리즘에서 시간을 줄이기 위해 리스트보다는 힙을 자료구조로 이용하였다. 따라서 모든 정점에서 다익스트라를 실행하지 않고 1번 부터 N번 정점 까지의 다익스트라를 총 두번 실행하면 된다.

 

 # 코드 

import sys,heapq

# 초기 무한대값
INF = 100000000000000000000


n, m = map(int, sys.stdin.readline().split())

# 인접 리스트 생성
adj = [[] for _ in range(n)]
for _ in range(m):
    a, b, c = map(int, input().split())
    adj[a-1].append([b-1, c])
    adj[b-1].append([a-1, c])
    
# 반드시 지나야 하는 두 정점 입력
x, y = map(int, sys.stdin.readline().split())

# dijkstra : depart 에서 시작하여 arrive 까지 가는데 드는 최소비용을 리턴하는 함수
def dijkstra(depart, arrive):
    dist = [INF]*n
    pq = []
    heapq.heappush(pq, (0, depart))
    dist[depart] = 0
    while pq:
        cost, now = heapq.heappop(pq)
        if dist[now] < cost:
            continue
        for nxt, ncost in v[now]:
            ncost += cost
            if dist[nxt] > ncost:
                dist[nxt] = ncost
                heapq.heappush(pq, (ncost, nxt))
    return dist[arrive]

# path1 : 1, x, y, n 순서일 때 최소 비용
# path2 : 1, y, x, n 순서일 때 최소비용
path1 = dijkstra(0, x-1) + dijkstra(x-1, y-1) + dijkstra(y-1, n-1)
path2 = dijkstra(0, y-1) + dijkstra(y-1, x-1) + dijkstra(x-1, n-1)

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