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

• 문제 : 백준 1504번 특정한 최단 경로

• 알고리즘 : 다익스트라

• 설명
  

  • 주어진 두 개의 노드를 거쳐 1번 노드에서 N번 노드로 방문하는 최단 경로 구하기
  • 노드, 에지 중복 가능
  • 1번 → 경유지1 → 경유지2 → N번
  • 1번 → 경유지2 → 경유지1 → N번
  • 두 가지 경로 가능
  • 1번, 경유지1, 경유지2를 시작으로 하는 세 개의 최단 거리 리스트 구하기
  • 도착이 불가능할 경유 -1
  • 가능할 경우 더 짧은 거리 출력

• 의문점

  • 책에서 processed라는 리스트를 둬서 최단 거리를 구한 노드인지 체크를 했는데 계속 오답
  • 다른 풀이와 비교해보고 이 리스트를 주석 처리하니 정답
  • 다익스트라 알고리즘에 대해 더 공부해야겠다.

• 출처 : https://www.acmicpc.net/problem/1504

• 코드

from collections import deque
import heapq


def dijkstra(start):
    dist_list = [float('inf')] * (n+1)
    dist_list[start] = 0
    hq = []
    heapq.heappush(hq, (0, start))
    # processed = [False] * (n+1)
    while hq:
        w, a = heapq.heappop(hq)
        # if processed[a]:
        #     continue
        # processed[a] = True
        for u in adj_list[a]:
            b, w = u
            if dist_list[b] > dist_list[a] + w:
                dist_list[b] = dist_list[a] + w
                heapq.heappush(hq, (w, b))
    return dist_list


def init():
    import sys
    ipt = sys.stdin.readline
    n, e = map(int, ipt().split())
    adj_list = [[] for _ in range(n+1)]
    for _ in range(e):
        a, b, c = map(int, ipt().split())
        adj_list[a].append((b, c))
        adj_list[b].append((a, c))
    goal1, goal2 = map(int, ipt().split())
    return n, adj_list, goal1, goal2


n, adj_list, goal1, goal2 = init()
dist_list1 = dijkstra(1)
dist_list2 = dijkstra(goal1)
dist_list3 = dijkstra(goal2)
dist1 = dist_list1[goal1] + dist_list2[goal2] + dist_list3[n]
dist2 = dist_list1[goal2] + dist_list3[goal1] + dist_list2[n]
if dist1 == float('inf') or dist2 == float('inf'):
    print(-1)
else:
    print(min(dist1, dist2))