14938 백준 파이썬

처음에 수색범위 만큼만 이동할 수 있는 줄 알고 삽질했던 문제;;

알고보니 수색범위안에 있는 곳은 모두 갈 수 있던 거였다.

 

플로이드-와샬을 통해 해결했다.

n에서 시작하여 모든 노드까지의 영역이 기록시켜서 1부터 n까지 수색범위를 넘지 않는 것들의 아이템 수를 더해주면 된다.

 

from collections import deque
n, d, r = map(int, input().split())
region = [0]
region.extend(list(map(int, input().split())))
m = [[999999 for _ in range(n + 1)] for _ in range(n + 1)]
for _ in range(r):
    a, b, c = map(int, input().split())
    m[a][b] = m[b][a] = c
for t in range(n+1):
    for x in range(n+1):
        for y in range(n+1):
            if x==y:
                m[x][y]=0
            elif m[x][y]>m[x][t]+m[t][y]:
                m[x][y]=m[x][t]+m[t][y]
ans=[]
for x in range(n+1):
    item=0
    for y in range(n+1):
        if m[x][y]<=d:
            item+=region[y]
    ans.append(item)
print(max(ans))