알고리즘 스터디 - 백준 12834번 : 주간 미팅

문제 해석

1. 월곡에 있는 KIST나 양재에 있는 씨알푸드 둘 중 하나에서 팀이 의논하게 됨
2. 한 사람의 거리 d = (집 - KIST까지의 최단 거리) + (집-씨알푸드까지의 최단 거리)인데 도달 할 수 없는 곳이 KIST라면 (집 - KIST까지의 최단 거리) = -1이다.
3. 첫째 줄 팀원의 수 N, 장소의 수 V, 도로의 수 E
4. 둘째 줄 KIST 위치 A, 씨알푸드 위치 B
5. 셋째 줄 N 명의 팀원의 위치
6. 넷째 줄 E 크기 만큼 도로의 양 끝 장소 a, b와 길이 l이 주어짐
7. 모든 사람의 d를 더한 최단 거리의 합을 출력

알고리즘 코드

import heapq

# 첫쨰줄
n, v, e = map(int, input().split())

# 둘째줄
destination = list(map(int, input().split()))

# 셋째줄
team_mate = list(map(int, input().split()))

# 넷째줄
graph = [[] for _ in range(v+1)]

# 시작, 끝, 가중치 입력받기
for _ in range(e):
    a, b, c = map(int, input().split())
    graph[a].append((b, c))
    graph[b].append((a, c))

# 다익스트라 함수
def dijkstra(start, distance):
    # 시작 노드의 거리는 0으로 설정
    distance[start] = 0
    queue = []
    heapq.heappush(queue, (distance[start], start))
    
    while queue:
        dist, node = heapq.heappop(queue)

        if distance[node] < dist:
            continue

        for next in graph[node]:
            weighted_distance = dist + next[1]
            if weighted_distance < distance[next[0]]:
                distance[next[0]] = weighted_distance
                heapq.heappush(queue, (weighted_distance, next[0]))

total_dis = 0

for i in range(n):
    KIST = 0
    FOOD = 0
    # 장소 기억해야되는데 팀원 수마다 새로 설정해줘야 함
    INF = 10001
    distances = [INF] * (v+1)
    dijkstra(team_mate[i], distances)
    if distances[destination[0]] == INF:
        KIST = -1
    if distances[destination[1]] == INF:
        FOOD = -1
    if distances[destination[0]] != INF:
        KIST = distances[destination[0]]
    if distances[destination[1]] != INF:
        FOOD = distances[destination[1]]
    
    total_dis = total_dis + KIST + FOOD

print(total_dis)