[Python] boj no. 14938 : 서강그라운드

Problem

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

Idea

각 떨어진 지점으로부터 최대 m 범위 안의 지점까지의 아이템만을 획득할 수 있다.

따라서 플로이드-워셜 알고리즘을 통해 각 지점 사이의 최단 거리를 모두 구한 뒤, 최단 거리 테이블을 탐색하며 각 지점마다 획득할 수 있는 아이템 수를 구했다.

Code

import sys

input = sys.stdin.readline

n, m, r = map(int, input().split())
item = list(map(int, input().split()))
weight = [[sys.maxsize for _ in range(n)] for _ in range(n)]
for i in range(n):
    weight[i][i] = 0
    
for _ in range(r):
    a, b, l = map(int, input().split())
    weight[a-1][b-1], weight[b-1][a-1] = l, l
    
for k in range(n):
    for i in range(n):
        for j in range(n):
            weight[i][j] = min(weight[i][j], weight[i][k]+weight[k][j])
    
sol = [0 for _ in range(n)]
for i in range(n):
    for j in range(n):
        if weight[i][j] <= m:
            sol[i] += item[j]
         
print(max(sol))

Comment