[파이썬] [최단경로] 백준 14938 서강그라운드

문제

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

14938번: 서강그라운드

 

코드

import sys
input=sys.stdin.readline
INF=sys.maxsize

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

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

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

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

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])

result=0
for i in range(1,n+1):
    temp=0
    for j in range(1,n+1):
        if graph[i][j]<=m:
            temp+=item[j-1]
    result=max(result,temp)

print(result)