문제

만약 KIST 기사단 2기로 여러분이 선발된다면, 서울 월곡에 있는 KIST와 양재에 있는 씨알푸드에서 팀이 함께 만나 의논하고 함께 작업할 시간을 가지게 된다. 누구나 그 회의 장소에 빨리 가고 싶은 마음은 똑같을 것이다.

각 장소를 노드로 생각하고, 연결된 도로를 간선으로 생각하면 그래프를 구성할 수 있다. KIST 기사단 N명의 집이 있는 노드 번호와 KIST, 씨알푸드의 노드 번호가 주어지고, 한 사람의 거리 di = (집-KIST의 최단 거리) + (집-씨알푸드의 최단 거리)로 정의된다. 단, 도달할 수 없는 경우의 최단 거리는 -1로 정의한다. 예를 들어, 어떤 사람이 KIST로는 갈 수 없고 씨알푸드까지의 최단 거리가 10인 경우 이 사람의 거리 d는 9이고, 다른 사람이 KIST, 씨알푸드로 모두 갈 수 없을 경우 이 사람의 거리 d는 -2이다. 이때 Σdi의 값을 출력하는 프로그램을 작성하시오.

# 12834
import sys
input = lambda : sys.stdin.readline().strip()
INF = int(1e9)

import heapq
n, v, e = map(int, input().split())
kist, food = map(int, input().split())
team = list(map(int, input().split()))

graph = [[] for _ in range(v+1)]
distance = [INF] * (v+1)

for _ in range(e):
    a, b, l = map(int, input().split())
    graph[a].append((b, l))
    graph[b].append((a, l))
    
def dijkstra(start):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0
    while q:
        dist, now = heapq.heappop(q)
        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(q, (cost, i[0]))
                
count = 0
for person in team:
    dijkstra(person)
    if distance[kist] == INF:
        count -= 1
    else:
        count += distance[kist]
    if distance[food] == INF:
        count -= 1
    else:
        count += distance[food]
    distance = [INF] * (v+1)
    
print(count)

백준 12834 주간 미팅