백준 14938 서강그라운드

import heapq
INF = int(1e9)

n, m, r = map(int, input().split())
t = list(map(int, input().split()))
g = [[] for _ in range(n)]

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

def dijkstra(s):
    d = [INF] * n
    q = []
    heapq.heappush(q, (0, s))
    d[s] = 0
    while q:
        dist, now = heapq.heappop(q)
        if d[now] < dist:
            continue
        for y, ndist in g[now]:
            cost = dist + ndist
            if d[y] >= cost:
                d[y] = cost
                heapq.heappush(q, (cost, y))
    return d

ans = 0
for i in range(n):
    dist = dijkstra(i)
    items = 0
    for i, d in enumerate(dist):
        if d <= m:
            items += t[i]
    ans = max(ans, items)
print(ans)

다익스트라로 최단거리를 탐색해서 그 중 탐색 가능한 곳에서 얻을 수 있는 아이템의 수의 최대값 구함
플로이드 와샬도 가능해보임