서강그라운드

접근

수색할 수 있는 범위가 정해져 있고 시작 위치가 정해져있지 않기 때문에 모든 노드 간의 관계에 대한 최단 거리가 얼마인지 구해야 한다. 플로이드 와샬 알고리즘의 시간 복잡도는 O(n^3), 노드 수가 100개 이하이기 때문에 해결 가능하다고 판단하였다.

tmp : 한 정점에 대해 수색 범위 안에 있는 정점들의 아이템 수의 합
rst : tmp의 최댓값

코드

import sys
input = sys.stdin.readline
INF = float('inf')

n, m, r = map(int, input().split())
arr = [0]+list(map(int, input().split()))
graph = [[INF] * (n+1) for _ in range(n+1)]
for _ in range(r):
    u, v, w = map(int, input().split())
    graph[u][v] = w
    graph[v][u] = w

for i in range(1, n+1):
    for j in range(1, n+1):
        if (i == j):
            graph[i][j] = 0

for k in range(1, n+1):
    for i in range(1, n+1):
        for j in range(1, n+1):
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])

rst = 0
for row in graph:
    tmp = 0
    for i in range(1, len(row)):
        if m >= row[i]:
            tmp += arr[i]
    rst = max(rst, tmp)

print(rst)