import sys
input = sys.stdin.readline
from collections import deque
INF = sys.maxsize
N,M,R = map(int,input().split())
item = deque(map(int,input().split()))
item.appendleft(0)
graph = [[INF]*(N+1) for i in range(N+1)]
for i in range(R):
x1,x2,r = map(int,input().split())
graph[x1][x2] = graph[x2][x1] = r
for k in range(1,N+1):
for i in range(1,N+1):
for j in range(1,N+1):
if i == j:
graph[i][i] = 0
if graph[i][j] > graph[i][k]+graph[k][j]:
graph[i][j] = graph[i][k]+graph[k][j]
value = [0]*(N+1)
for i in range(1,N+1):
for j in range(1,N+1):
if graph[i][j] <= M:
value[i] += item[j]
print(max(value))
바로 좀전에 배웠던 플로이드 알고리즘을 이용하면 너무나 쉽게 풀 수 있는 문제이다.
푸는데 5분도 안걸린듯;
역시 알고리즘은 많이 알고봐야 한다.
오늘의 교훈) 알고리즘 공부를 하자