백준 온라인 저지, 최단경로 / 12834번: 주간미팅 (파이썬 / , 백준 골드문제)

문제

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

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

입력

첫째 줄에 KIST 기사단 팀원의 수 N, 장소의 수 V, 도로의 수 E가 주어진다. (N ≤ 100, V ≤ 1000, E ≤ 10000)

둘째 줄에 KIST의 위치 A와 씨알푸드의 위치 B가 주어진다. (1 ≤ A, B ≤ V)

셋째 줄에 팀원 N명의 집의 위치 H_i가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ H_i ≤ V)

넷째 줄부터 E+3번째 줄까지는 도로의 양 끝 장소 a, b와 길이 l이 주어진다. (1 ≤ a, b ≤ V, 1 ≤ l ≤ 100)

출력

모든 사람의 최단 거리의 합을 출력한다. 단, KIST나 씨알푸드로 갈 수 없는 경우에는 -1로 처리한다.

제한

예제 입력 1

2 5 10
3 5
2 4
3 2 91
1 3 44
5 3 93
1 4 1
4 5 53
4 2 23
5 1 60
2 1 63
3 4 38
5 2 17

예제 출력 1

156

힌트

접근 방법

- 1. KIST의 위치와 씨알푸드의 위치로부터 다른 장소의 위치까지의 거리를 다익스트라 최단경로 알고리즘을 활용해 구한다.(위의 간선은 양방향임)
- 2. 각 위치는 KIST와 씨알푸드의 거리 값을 기준으로 이중리스트로 구성하여 이를 처리한다.

코드

# https://www.acmicpc.net/problem/12834
# 접근 방법
# 1. KIST의 위치와 씨알푸드의 위치로부터 다른 장소의 위치까지의 거리를 다익스트라 최단경로 알고리즘을 활용해 구한다.(위의 간선은 양방향임)
# 2. 각 위치는 KIST와 씨알푸드의 거리 값을 기준으로 이중리스트로 구성하여 이를 처리한다.
def dijkstra(start, idx):
    distance[start][idx] = 0
    h = []
    heapq.heappush(h, [0, start])
    while h:
        dist, now = heapq.heappop(h)
        if distance[now][idx] < dist:
            continue
        for x in graph[now]:
            cost = x[1] + dist
            if distance[x[0]][idx] > cost:
                distance[x[0]][idx] = cost
                heapq.heappush(h, [cost, x[0]])


import sys, heapq
input = sys.stdin.readline
n, v, e = map(int, input().split())
A, B = map(int, input().split())
h = list(map(int, input().split()))
graph = [[] for _ in range(v+1)]
for _ in range(e):
    a, b, l = map(int, input().split())
    graph[a].append([b, l])
    graph[b].append([a, l])
INF = int(1e8)
distance = [[INF, INF] for _ in range(v+1)]
dijkstra(A, 0)
dijkstra(B, 1)
result = 0
for i in h:
    if distance[i][0] == INF:
        distance[i][0] = -1
    if distance[i][1] == INF:
        distance[i][1] = -1
    result += distance[i][0] + distance[i][1]
print(result)