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

💡문제접근

• 개선된 다익스트라 알고리즘을 변형한 문제라 고민을 많이 했던 다익스트라 알고리즘 응용문제
• 1 → N으로 이동할 때 주어진 두 정점을 반드시 거치면서 최단 경로로 이동하는 경우는 2가지가 존재한다.
  ①. 1 → V1 → V2 → N
  ②. 1 → V2 → V1 → N
• 처음에 코드를 제출했는데 75%에서 WA를 받아서 그 이유가 무엇인지 고민하다가 질문게시판을 참고했는데 간선이 존재하지 않는 경우도 고려해야한다고 했다.
• 방향성이 있는 그래프인지 방향성이 없는 그래프인지를 먼저 파악하자.
• 방향성이 없는 그래프의 경우 양방향을 모두 저장해야하고 방향성이 있는 그래프의 경우 단방향만 저장해주면 된다.

💡코드(메모리 : 68500KB, 시간 : 608ms)

import heapq
import sys
input = sys.stdin.readline
INF = int(1e9)

N, E = map(int, input().strip().split())
start = 1
graph = [[] for _ in range(N+1)]

for _ in range(E):
    a, b, c = map(int, input().strip().split())
    graph[a].append([b, c])
    graph[b].append([a, c])
V1, V2 = map(int, input().strip().split())

def dijkstra(start):
    queue = []
    heapq.heappush(queue, (0, start))
    distance = [INF] * (N + 1)
    distance[start] = 0
    while queue:
        dist, now = heapq.heappop(queue)
        if distance[now] < dist:
            continue
        for i in graph[now]:
            cost = dist + i[1]
            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(queue, (cost, i[0]))
    return distance

start_path = dijkstra(start)
v1_path = dijkstra(V1)
v2_path = dijkstra(V2)

# 1, V1, V2를 거치는 경로 : 1 → V2 → V1 → N
# 1, V1, V2를 거치는 경로 : 1 → V1 → V2 → N
v1_result = start_path[V1] + v1_path[V2] + v2_path[N]
v2_result = start_path[V2] + v2_path[V1] + v1_path[N]

if v1_path[V2] == INF or v2_path[N] == INF or v2_path[V1] == INF or v1_path[N] == INF:
    print(-1)
else:
    print(min(v1_result, v2_result))

💡소요시간 : 44m