[Python][BOJ 14938] 서강그라운드

 

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

14938번: 서강그라운드

 

 

 플로이드 워셜, 데이크스트라, 브루트포스의 응용문제다. 나는 플로이드 워셜을 사용했는데, 각 정점에서 다른 정점으로 가는 길이를 모두 구해놓고 탐색 범위 m보다 길이가 작은 수들의 아이템 개수를 저장하고, 각 정점에서 모을 수 있는 아이템 개수들 중에서 최대값을 출력하면 되는 문제다.

 

코드는 아래에 있다.

n,m,r=map(int,input().split())
t=[0]+list(map(int,input().split()))

d=[[1e9 for _ in range(n+1)]for _ in range(n+1)]

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

for i in range(1,n+1):
    d[i][i]=0

for _ in range(r):
    a,b,l=map(int,input().split())
    d[a][b]=l
    d[b][a]=l

floid()

ans=[0 for _ in range(n+1)]
for i in range(1,n+1):
    for j in range(1,n+1):
        if d[i][j]>m:
            continue
        ans[i]+=t[j]

print(max(ans))