백준 온라인 저지 📌 특정한 최단 경로

📌 특정한 최단 경로

• 문제는 어렵지 않았습니다.
• 문제에서 지정하는 임의의 2개의 노드를 무조건 지나야 하면서 노드 1부터 노드 N까지 최단거리로 도착하는 알고리즘을 짜는 것이었습니다.
• 따라서 다익스트라 알고리즘을 구현하고 임의의 노드 중 어떤 노드를 먼저 방문해야 최단 거리가 되는지 알아가면 됩니다.
• 추가적으로 도착할 수 없으면 -1을 출력하라는 문제의 조건을 지치면 바로 통과되는 그런 난이도였습니다.

import sys
from heapq import heappop, heappush
input = sys.stdin.readline

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

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

node1, node2 = map(int, input().split())

def dijkstra(s, e):
    INF = int(1e9)
    distance = [INF] * (N+1)
    distance[s] = 0

    heap = []
    heappush(heap, (0, s))

    while heap:
        dist, now = heappop(heap)

        if dist > distance[now]:
            continue

        for nxt, dis in graph[now]:
            cost = dist + dis

            if cost < distance[nxt]:
                distance[nxt] = cost
                heappush(heap, (cost, nxt))
    
    return distance[e]


if dijkstra(1, N) == int(1e9):
    print(-1)
else:
    answer = min(dijkstra(1, node1) + dijkstra(node1, node2) + dijkstra(node2, N), dijkstra(1, node2) + dijkstra(node2, node1) + dijkstra(node1, N))
    print(answer)

• 코드만 보아도 어떤 느낌인지 바로 오실겁니다. 오늘 알고리즘 풀이는 여기서 끝!