[Python/파이썬] 백준 14938번: 서강그라운드

문제

풀이

다익스트라 방법과 플로이드-와샬 방법이 있는데, 

노드의 개수가 적어서 플로이드-와샬 방법으로 풀었다.

 

플로이드-와샬 알고리즘을 안다면 쉽게 풀 수 있는 문제이므로 풀이는 생략함.

 

코드

from sys import stdin
input = stdin.readline

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

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

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

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

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][k] + graph[k][j], graph[i][j])

maxItem = 0
for g in graph:
      tmp = 0
      for i in range(1, n + 1):
            if g[i] <= m:
                  tmp += items[i - 1]
      maxItem = max(maxItem, tmp)

print(maxItem)

 

마무리

플로이드-와샬... 이해는 완벽히 했는데 아직 암기가 덜 된 것 같다.. ㅠㅠ