백준 1504 특정한 최단 경로 파이썬

🔗 [백준]1504 특정한 최단 경로 

📌오늘의 학습 키워드

• 다익스트라 짬뽕

✨공부한 내용 본인의 언어로 정리하기

• 다익스트라를 사용하는 문제라고 인식했다.
• 각 정점 별로 start ➡️ v1, v1 ➡️ v2, v2 ➡️ end 까지의 다익스트라 값을 더한다.
• 최소값을 찾는다.

📚오늘의 회고

• 다익스트라를 구현할 때 자료구조를 deque로 했다가 heap으로 고쳤다. 
• 1 ➡️ v1 ➡️ v2 ➡️ end 말고 1 ➡️ v2 ➡️ v1 ➡️ end 를 고려하지 않아서 고쳤다.
• 각각의 전체 값을 구하는 과정에서 다익스트라(start, end) 이런식으로 구해서 더해주려고 했으나 그냥 각 점에서의 전체 다익스트라값을 구하고 인덱스를 찾는 방식으로 고쳤다.

[🤓문제 해결 코드]

import heapq
from heapq import heappush
import sys

N, E = map(int, input().split())
graph = [[] for _ in range(N + 1)]
for n 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())

def dijkstra(start):
    distance = [sys.maxsize for _ in range(N + 1)]
    distance[start] = 0
    hq = []
    heappush(hq, (start, 0))

    while hq:
        node, dist = heapq.heappop(hq)
        if dist > distance[node]:
            continue

        for next_n, value in graph[node]:
            new_dist = dist + value
            if new_dist < distance[next_n]:
                distance[next_n] = new_dist
                heapq.heappush(hq, (next_n, new_dist))

    return distance

dist_from_1 = dijkstra(1)
dist_from_v1 = dijkstra(v1)
dist_from_v2 = dijkstra(v2)

# 1 -> v1 -> v2 -> N
path1 = dist_from_1[v1] + dist_from_v1[v2] + dist_from_v2[N]
# 1 -> v2 -> v1 -> N
path2 = dist_from_1[v2] + dist_from_v2[v1] + dist_from_v1[N]

result = min(path1, path2)
if result >= sys.maxsize:
    print(-1)
else:
    print(result)