백준 1504 특정한 최단 경로

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

1504번: 특정한 최단 경로

📌 해결순서

다익스트라 기본 문제와 매우 비슷한 문제, 조금 조건만 추가 됐다.

 

최단경로를 구하는 것은 동일 하지만, 지정한 두 정점을 무조건 거쳐야 하므로

두 정점에서 출발하여 다른 모든 노드로 가는 최단경로 테이블을 각각 만들어 주면 쉽게 해결할 수 있겠다고 생각했다.

테이블을 총 3개 만들어야 하니까, 함수 호출을 3번 해주면 되겠군.. 이렇게 생각해봄

각각의 테이블은 최단경로만 저장을 하니까 테이블만 구해놓으면 굉장히 쉽게 풀수 있는 문제 였다.

 

1번에서 n번 정점을 지정한 두 정점을 무조건 거쳐서 가는 방법은 2가지다

 

1 -> 정점1 -> 정점2 -> n

1 -> 정점2 -> 정점1 -> n

 

둘 중에, 최솟값을 출력해주면 된다.

 

📌 코드

import heapq
import sys

input = sys.stdin.readline
INF = sys.maxsize
n, e = map(int, input().split())
graph = [[] for _ in range(n + 1)]

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

v1, v2 = map(int, input().split())

distance_start = [INF] * (n + 1)
distance_v1 = [INF] * (n + 1)
distance_v2 = [INF] * (n + 1)


def dijkstra(start, distance):
    q = []
    distance[start] = 0
    heapq.heappush(q, (0, start))

    while q:
        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in graph[now]:
            cost = distance[now] + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(1, distance_start)
dijkstra(v1, distance_v1)
dijkstra(v2, distance_v2)

ans = min(distance_start[v1] + distance_v1[v2] + distance_v2[n],
          distance_start[v2] + distance_v2[v1] + distance_v1[n])

print(ans if ans < INF else -1)