[백준 14938번] 서강그라운드 (Python3)

import sys
input = sys.stdin.readline
from collections import deque
INF = sys.maxsize

N,M,R = map(int,input().split())

item = deque(map(int,input().split()))
item.appendleft(0)

graph = [[INF]*(N+1) for i in range(N+1)]

for i in range(R):
  x1,x2,r = map(int,input().split())
  graph[x1][x2] = graph[x2][x1] = r

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

value = [0]*(N+1)

for i in range(1,N+1):
  for j in range(1,N+1):
    if graph[i][j] <= M:
      value[i] += item[j]

print(max(value))

바로 좀전에 배웠던 플로이드 알고리즘을 이용하면 너무나 쉽게 풀 수 있는 문제이다.

푸는데 5분도 안걸린듯;

역시 알고리즘은 많이 알고봐야 한다.

 

 

오늘의 교훈) 알고리즘 공부를 하자