[BOJ] 14938. 서강그라운드 (🥇, 최단거리)

🔗

풀이

이 문제에서 가중치는 거리이며, 특정 위치에서 다른 모든 위치로 이동할 수 있는 거리를 모두 구하는대신 m을 넘어가면 더 이상 구하지 않는다. m이하에 있는 위치들의 아이템을 다 더해서 나오는 최대값을 구하는 문제. 다익스트라로 풀이했다.

# 60ms

import heapq

def dijkstra(i):
    dist = [1e9]*n
    dist[i] = 0
    Q = [(0, i)]

    while Q:
        d, node = heapq.heappop(Q)

        if d > m or d > dist[node]:
            continue

        dist[node] = d
        for v, w in graph[node]:
            heapq.heappush(Q, (d+w, v))

    return [i for i in range(len(dist)) if dist[i] != 1e9]

n, m, r = map(int, input().split())
item = list(map(int, input().split()))

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

ans = 0
for i in range(n):
    ans = max(ans, sum(item[i] for i in dijkstra(i)))

print(ans)