백준 알고리즘 1504: 특정한 최단 경로(Python)

www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

---

문제 해결을 위한 과정

이 문제의 경우 다익스트라 알고리즘을 이용하면 쉽게 해결할 수 있는 문제였습니다. 그러나 주의할 점이 있었는데 바로 꼭 거쳐야하는 2개의 지점이 있다는것 입니다. 지나가야 하는 지점이 x, y라 할 경우

1 -> x -> y -> N

1 -> y -> x -> N 

이렇게 두가지의 경우가 있으므로 위의 두가지 경우에 대한 다익스트라 알고리즘을 적용하여 거리를 각각 구한 후 더 작은 숫자를 출력하면 됩니다. 또한 문제에서 이동할 수 없는 거리라면 -1을 출력하라는 조건이 있었기 때문에 이를 유의하여 해결합니다.

---

소스코드

import heapq
INF = 1001
 
n, m = map(int, input().split())
graph = [[] for _ in range(1 + n)]
 
for i in range(m):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))
 
def dijkstra(start, pos):
    distance = [INF] * (1 + n)
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))
       
    return distance[pos]
x, y = map(int, input().split())
dist1 = dijkstra(1, x)
dist2 = dijkstra(x, y)
dist3 = dijkstra(y, n)
 
dist4 = dijkstra(1, y)
dist5 = dijkstra(y, x)
dist6 = dijkstra(x, n)
 
ans = min(dist1 + dist2 + dist3, dist4 + dist5 + dist6)
if ans >= INF:
    print(-1)
else:
    print(ans)