# BOJ - 14938 - 서강그라운드

Updated:

```
import sys
from heapq import heappush, heappop
def Dijkstra(K, graph, V):
heap = []
distance = [1e9] * (V + 1)
distance[K] = 0
heappush(heap, (0, K))
while heap:
weight, location = heappop(heap)
if distance[location] < weight:
continue
for l, w in graph[location]:
w += weight
if w < distance[l]:
distance[l] = w
heappush(heap, (w, l))
return distance
def solution():
N, M, R = map(int, sys.stdin.readline().split())
graph = [[] for _ in range(N + 1)]
item = list(map(int, sys.stdin.readline().split()))
for _ in range(R):
u, v, w = map(int, sys.stdin.readline().split())
graph[u].append([v, w])
graph[v].append([u, w])
ret = 0
for idx in range(1, N+1):
arr = Dijkstra(idx, graph, N)
temp = 0
for jdx in range(N):
temp += item[jdx] if arr[jdx+1] <= M else 0
ret = max(ret, temp)
print(ret)
solution()
```

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

## Leave a comment