[알고리즘][Python] 백준 1504 특정한 최단 경로 문제 풀이

문제 출처 : www.acmicpc.net/problem/1504

1504번: 특정한 최단 경로

---

문제 해석 : 1에서 N 까지 이동할 때 항상 두 지점을 지나야한다. 이때 최단 경로로 움직일 때 그 거리를 구하는 문제이다.

 

문제 풀이 : 다익스트라 알고리즘을 적용해서 풀 수 있다. 가능한 경우의 수는 2가지 이다.

: must1 -> must2

: must2 -> must1

 

이 둘 중에 최단 거리를 고른다.

 

이때 갈 수 없는 경로 일 경우에는 -1을 출력하는 것에 유의하자.

---

풀이 코드

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


def dijkstra(start_node, end):
    distance = [INF] * (N + 1)

    Q = []
    heapq.heappush(Q, (0, start_node))
    distance[start_node] = 0

    while Q:
        now_dist, now_node = heapq.heappop(Q)

        for next_dist, next_node in graph[now_node]:
            next_dist = next_dist + now_dist

            if next_dist < distance[next_node]:
                distance[next_node] = next_dist
                heapq.heappush(Q, [next_dist, next_node])

    return distance[end]


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

graph = [[] for _ in range(N+1)]

for _ in range(E):
    start, end, cost = map(int, input().split())

    graph[start].append([cost,end])
    graph[end].append([cost,start])

must1, must2 = map(int, input().split())

temp1 = dijkstra(1, must1) + dijkstra(must1, must2) + dijkstra(must2, N)
temp2 = dijkstra(1, must2) + dijkstra(must2, must1) + dijkstra(must1, N)

if temp1 >= INF and temp2 >= INF:
    print(-1)
else:
    print(min(temp1, temp2))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.