[ 14938 ] [ Dijkstra ] 서강그라운드

https://www.acmicpc.net/submit/14938

로그인

---

풀이 과정

---

1. 사실 이 문제는 다익스트라 알고리즘보다는 플로이드 알고리즘으로 풀이하는게 훨씬 쉽고 간단하게 풀린다. 다익스트라 알고리즘을 연습하고자 사용하였음..
2. 시작점을 1~n까지 각각의 지점에서 다익스트라 알고리즘을 적용한다.
   1. 최소 히프를 사용하여, 현재 갈수있는 노드 중 길이가 최소인 노드를 방문한다.
   2. 현재 노드를 거쳐갈때의 거리로 인접 노드들의 거리를 갱신할 수 있으면 갱신 후 히프에 해당 노드를 넣어준다.  
   3. 1-2를 반복하다 보면 히프에 같은 노드가 쌓일수도 있다. 따라서 히프에 저장된 길이와 현재 저장된 길이를 비교해준 다음, 다른 경우는 최솟값이 갱신된 경우이므로 그냥 넘어간다.
3. 다익스트라 알고리즘이 종료되면 거리가 m 이내인 지점의 모든 아이템의 개수를 더한 후, 최대 아이템 개수를 갱신한다.
4. 최대 아이템 개수를 출력한다.

---

소스 코드

---

import sys
import heapq

INT_MAX = int(10e9)
input = lambda: sys.stdin.readline().rstrip()

n, m, r = map(int, input().split())
item_count = [0] + list(map(int, input().split()))
graph = [[] for _ in range(n+1)]

for _ in range(r):
    a, b, l = map(int, input().split())
    graph[a].append([b, l])
    graph[b].append([a, l])

answer = 0

# 전체 지점에서 시작해본 다음, 아이템을 몇개 구할수 있는지 구한다.
# 이후 최대 아이템의 개수 갱신
for start in range(1, n+1):
    distance = [INT_MAX] * (n+1)
    distance[start] = 0
    heap = []
    heapq.heappush(heap, [0, start])

    while heap:
        node, dist = heapq.heappop(heap)
        if distance[node] != dist:
            continue

        for next_node, next_distance in graph[node]:
            if distance[next_node] > distance[node] + next_distance:
                distance[next_node] = distance[node] + next_distance
                heapq.heappush(heap, [distance[next_node], next_node])
    
    total_item_count = sum([item_count[i] for i in range(1, n+1) if distance[i] <= m])
    answer = max(answer, total_item_count)

print(answer)