1. 문제 설명

두 단계 최단 경로 2

2. 문제 분석

특정 노드를 경유하는 최단 경로는 도착지와 목적지에서 각각 돌린 다익스트라 알고리즘으로 구한 최단 경로 배열에서 그 노드를 사용하는 거리 두 개의 합이다.

3. 나의 풀이

import sys
import heapq

INF = sys.maxsize
n, m = map(int, sys.stdin.readline().rstrip().split())
nodes = [[] for _ in range(n+1)]
for _ in range(m):
    a, b, c = map(int, sys.stdin.readline().rstrip().split())
    nodes[a].append([b, c])
    nodes[b].append([a, c])
x, z = map(int, sys.stdin.readline().rstrip().split())
p = int(sys.stdin.readline().rstrip())
y_nodes = set(map(int, sys.stdin.readline().rstrip().split()))

def Dijkstra(start):
    distances = [INF for _ in range(n+1)]
    distances[start] = 0
    pq = []
    heapq.heappush(pq, [0, start])

    while pq:
        cur_cost, cur_node = heapq.heappop(pq)
        if distances[cur_node] < cur_cost: continue

        for next_node, next_cost in nodes[cur_node]:
            if distances[next_node] > next_cost + cur_cost:
                distances[next_node] = next_cost + cur_cost
                heapq.heappush(pq, [next_cost + cur_cost, next_node])

    return distances

answer = INF

distances_x = Dijkstra(x)
distances_z = Dijkstra(z)

for y in y_nodes:
    answer = min(distances_x[y] + distances_z[y], answer)

if answer == INF: print(-1)
else: print(answer)