[BOJ 12834🥇4] 주간 미팅 (Python)

https://www.acmicpc.net/problem/12834

12834번: 주간 미팅

문제

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

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

입력

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

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

셋째 줄에 팀원 N명의 집의 위치 Hi가 공백을 사이에 두고 주어진다. (1 ≤ i ≤ N, 1 ≤ Hi ≤ 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

 

⭕ CODE

import sys

input = sys.stdin.readline

import heapq

# 팀원의수 n, 장소의 수 v, 도로의 수 e
n, v, e = map(int, input().split())

# kist의 위치 a, cr위치 b
a, b = map(int, input().split())

# 팀원 n명의 집의 위치 h_i
house = list(map(int, input().split()))

inf = int(1e9)

arr = [[] for i in range(v + 1)]

distance_a = [inf] * (v + 1)
distance_b = [inf] * (v + 1)

for _ in range(e):
    # 도로의 양 끝 장소 x,y 길이 l
    x, y, l = map(int, input().split())
    # x에서 y로 가는 길이가 l이다.
    # 양방향이므로
    # y에서 x로 가는 길이도 l이다.
    arr[x].append((y, l))
    arr[y].append((x, l))


def dijkstra(start, distance):
    q = []
    heapq.heappush(q, (0, start))
    distance[start] = 0

    while q:

        dist, now = heapq.heappop(q)

        if distance[now] < dist:
            continue

        for i in arr[now]:
            cost = dist + i[1]

            if cost < distance[i[0]]:
                distance[i[0]] = cost
                heapq.heappush(q, (cost, i[0]))


dijkstra(a, distance_a)
dijkstra(b, distance_b)

result = 0

# 각각 도달할 수 없는 경우 -1로 지정
for i in house:
    if distance_a[i] == inf:
        distance_a[i] = -1
    if distance_b[i] == inf:
        distance_b[i] = -1

    result += distance_a[i] + distance_b[i]

print(result)

✏️ Comment

KIST와 씨알푸드의 위치가 고정되어 있어 우리가 알 수 있으므로 다익스트라 알고리즘을 사용하여 각각의 집들과의 거리를 구하여 문제를 해결하였다.