[백준] 1504. 특정한 최단 경로/Python - Gold4

❓문제

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

성능 요약

메모리: 126204 KB, 시간: 376 ms

분류

그래프 이론, 최단 경로, 데이크스트라

문제 설명

방향성이 없는 그래프가 주어진다. 세준이는 1번 정점에서 N번 정점으로 최단 거리로 이동하려고 한다. 또한 세준이는 두 가지 조건을 만족하면서 이동하는 특정한 최단 경로를 구하고 싶은데, 그것은 바로 임의로 주어진 두 정점은 반드시 통과해야 한다는 것이다.

세준이는 한번 이동했던 정점은 물론, 한번 이동했던 간선도 다시 이동할 수 있다. 하지만 반드시 최단 경로로 이동해야 한다는 사실에 주의하라. 1번 정점에서 N번 정점으로 이동할 때, 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 프로그램을 작성하시오.

✍🏻풀이

우선 주어진 그래프가 방향성이 없는 그래프이므로 간선을 양방향 모두 기록한다.

그리고 기록한 간선 정보를 바탕으로 주어진 두 정점을 지나는 최단 경로를 이동하는 길이를 구한다. 그리고 최단 경로를 구하기 위해 다익스트라 알고리즘을 사용한다.

두 정점을 지나는 경로는 1 ➡️ v1 ➡️ v2 ➡️ N, 1 ➡️ v2 ➡️ v1 ➡️ N 두 가지 경우가 있다. 그러므로 1 ➡️ v1, v1 ➡️ v2, v2 ➡️ N 과  1 ➡️ v2, v2 ➡️ v1, v1 ➡️ N 각각의 최단 경로를 구해서 출력하면 된다. 이때 두 가지 경우로 거리를 구했을 때 INF보다 같거나 크면 -1을 출력한다.

💻코드

import sys
from heapq import heappush, heappop

input = sys.stdin.readline
INF = 1e9

N, E = map(int, input().split())
edges = [[] for _ in range(N)]
for _ in range(E):
    a, b, c = map(int, input().split())
    edges[a-1].append((b-1, c))
    edges[b-1].append((a-1, c))
v1, v2 = map(int, input().split())

def dijkstra(start, end):
    dist = [INF] * N
    move = [(0, start)]
    dist[start] = 0
    
    while move:
        d, v = heappop(move)
        for u, c in edges[v]:
            if dist[u] > d + c:
                dist[u] = d + c
                heappush(move, (d + c, u))
    
    return dist[end]

# 1 -> v1 -> v2 -> N
c1 = dijkstra(0, v1-1) + dijkstra(v1-1, v2-1) + dijkstra(v2-1, N-1)

# 1 -> v2 -> v1 -> N
c2 = dijkstra(0, v2-1) + dijkstra(v2-1, v1-1) + dijkstra(v1-1, N-1)

print(-1) if c1 >= INF and c2 >= INF else print(min(c1, c2))

📍후기

나눠서 구하는 것 까지는 생각했는데 중간에 헤매서 푸는데 오래 걸렸다...