[#알고리즘/최단 경로/[백준]14938번: 서강 그라운드(python)]

Question

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

Solution

플로이드 워셜 알고리즘을 이용하여 쉽게 풀 수 있는 문제였다. 우선 A에서 B로 가는 비용이 C라면, B에서 A로 가는 비용 또한 C이다. 플로이드 워셜 알고리즘을 수행하여 모든 노드에서 다른 모든 노드로 갈 수 있는 경로의 비용 정보를 완성한다. 그 후 각 노드에 떨어진 경우, 떨어진 노드에서 출발하여 수색범위 내에 갈 수 있는 노드들의 아이템 수를 합했을 때, 어떠한 노드에 떨어져야 가장 많은 아이템을 얻을 수 있는 지 그 최댓값을 찾아낸다.

Code

import sys

input = sys.stdin.readline
INF = int(1e9)

# 지역 개수, 수색 범위, 길의 개수
n, m, r = map(int, input().split())
# 각 구역에 있는 아이템 수
item = list(map(int, input().split()))

# 2차원 리스트를 만들고, 모든 값을 무한으로 초기화
graph = [[INF] * (n + 1) for _ in range(n + 1)]

# 자기 자신에서 자신으로 가는 비용은 0
for a in range(1, n + 1) :
    for b in range(1, n + 1) :
        if a == b :
            graph[a][b] = 0
            
# 각 간선에 대한 정보를 입력받기
for _ in range(r) :
    # A에서 B로 가는 비용은 C
    a, b, c = map(int, input().split())
    graph[a][b] = c
    graph[b][a] = c

# 점화식에 따라 플로이드 워셜 알고리즘 수행
for k in range(1, n + 1) :
    for a in range(1, n + 1) :
        for b in range(1, n + 1) :
            graph[a][b] = min(graph[a][b], graph[a][k] + graph[k][b])
                

max = 0
for a in range(1, n + 1) :
    sum = 0
    for b in range(1, n + 1) :
        if graph[a][b] <= m :
            sum += item[b-1]
    if sum > max :
        max = sum
        
print(max)