백준 14938 <서강그라운드> Python

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

---

플로이드-워셜 알고리즘 문제입니다.

 

모든 노드에서 모든 노드로의 최단거리를 구해주기 위해 다익스트라가 아닌 플로이드-워셜 알고리즘을 사용합니다. 모든 최단거리를 구했다면 각 최단거리 중 도달할 수 있는 거리보다 작은 거리만 필터링해 해당하는 노드의 아이템 합을 구해 비교해주면 풀 수 있습니다.

---

import sys

input = sys.stdin.readline


def solution(n, m, r, items, edges):
    ## 플로이드-워셜
    # 최단거리 리스트
    min_dists = [[float('inf') for _ in range(n+1)] for __ in range(n+1)]
    for i in range(n+1):
        min_dists[i][i] = 0
    
    for a, b, l in edges:
        min_dists[a][b] = min(min_dists[a][b], l)
        min_dists[b][a] = min(min_dists[b][a], l)
    
    # 중간 노드
    for mid in range(1, n+1):
        # 출발 노드
        for front in range(1, n+1):
            # 도착 노드
            for back in range(1, n+1):
                # 갱신
                min_dists[front][back] = min(min_dists[front][back], min_dists[front][mid] + min_dists[mid][back])
    
    ## 각 지역에서 도달할 수 있는 지역들 / 아이템 합 찾기
    # 도달할 수 있는 지역
    reachable_nodes = [[j for j in range(1, len(min_dists[i])) if min_dists[i][j] <= m] for i in range(1, n+1) ]
    # 아이템 합
    sum_items = [sum(items[node] for node in reachable_node) for reachable_node in reachable_nodes]
    
    print(max(sum_items))


# 입력
n, m, r = map(int, input().strip().split())
items = [0] + list(map(int, input().strip().split()))
edges = [list(map(int, input().strip().split())) for _ in range(r)]

solution(n, m, r, items, edges)