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

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

1504번: 특정한 최단 경로

 

<코드>

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

INF = int(1e9)
graph = [[] for _ in range(N+1)]
q = []
for _ in range(E):
    a,b,c = map(int, input().split())
    graph[a].append((c, b))
    graph[b].append((c, a))

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

def dijkstra(s):
    start = [INF] * (N + 1)
    start[s] = 0
    heapq.heappush(q, (0, s))
    while q:
        d, current = heapq.heappop(q)

        if d > start[current]:
            continue

        for dis, next in graph[current]:
            distance = d + dis
            if start[next] > distance:
                start[next] = distance
                heapq.heappush(q, (distance, next))
    return start

first_node = dijkstra(1)
v1_node = dijkstra(v1)
v2_node = dijkstra(v2)
a = first_node[v1] + v1_node[v2] + v2_node[N]
b = first_node[v2] + v2_node[v1] + v1_node[N]
result = min(a, b)
if result >= INF:
    print(-1)
else:
    print(result)

 

<풀이방법>

다익스트라 알고리즘을 이용해서 출발노드에서의 최단 거리 테이블을 구하여서 풀었다.

 

<리뷰>

처음에 start테이블을 계속 초기화 해주지 않아서 틀렸었다.

다익스트라 문제를 몇개 풀다보니 이제 바로바로 풀이가 나오는 느낌이 든다.