[BOJ] 파이썬 1504번_특정한 최단경로

문제링크

풀이

import heapq
import sys
input = lambda: sys.stdin.readline().strip()
inf = 10e6
n,e = map(int,input().split())

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

for _ in range(e):
    fro, to, cost = map(int,input().split())
    graph[fro].append((to,cost))
    graph[to].append((fro, cost))

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


def solve(start):
    heap = []
    visited = [False for _ in range(n + 1)]
    dist = [inf for _ in range(n+1)]
    dist[start] = 0
    heapq.heappush(heap, (0, start))
    while heap:

        current_cost, current = heapq.heappop(heap)
        visited[current] = True
        for next, cost in graph[current]:
            if dist[next] > dist[current] + cost:
                dist[next] = dist[current] + cost
                heapq.heappush(heap, (dist[next], next))

    return dist


one_to_n = solve(1)
v1_to_n = solve(v1)
v2_to_n = solve(v2)


ans = min(one_to_n[v1] + v1_to_n[v2] + v2_to_n[n], one_to_n[v2] + v2_to_n[v1] + v1_to_n[n])

if ans >= 10e6:
    print(-1)
else:
    print(ans)
    

다익스트라 최단 경로 문제
주어진 두 정점(v1,v2)을 반드시 거치면서 최단 경로로 이동해야하므로,

• 정점 1 을 시작으로,
• 정점 v1을 시작으로
• 정점 v2를 시작으로

총 3번 다익스트라 알고리즘을 돌려줘서 거리 배열들을 계산한 후 1-v1-v2-n, 1-v2-v1-n 의 거리 중 더 작은 것이 정답.