BOJ - 14938

백준 문제 링크
서강그라운드

❓접근법

1. 플로이드 워셜 알고리즘을 사용했다.
2. 기본 플로이드 워셜 소스코드처럼
   자기 자신은 0으로,
   양방향이므로 graph[a][b], graph[b][a] 각각 l 을 지정한다.
3. 그 후 2중 반복문으로 answer를 갱신한다.

answer = 0
for i in range(1, n + 1):
    cnt = 0
    for j in range(1, n + 1):
        if graph[i][j] <= m:
            cnt += items[j-1] 
    answer = max(answer, cnt)
print(answer)

👌🏻코드

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

INF = int(1e9)

graph = [[INF] * (n + 1) for _ in range(n + 1)]

for a in range(1, n + 1):
    for b in range(1, n + 1):
        if a == b:
            graph[a][b] = 0
            
items = list(map(int, input().split()))

answer = [0] * (n + 1)

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

answer = 0

for i in range(1, n + 1):
    cnt = 0
    for j in range(1, n + 1):
        if graph[i][j] <= m:
            cnt += items[j-1] 
            
    answer = max(answer, cnt)
    
print(answer)