14938. 서강그라운드 (Python)

14938번: 서강그라운드

 

풀이

 최단거리를 활용하는 문제인데 시작점이 주어지지 않는다. 그렇기 때문에 모든 지점에서 다른 지점까지의 최단 거리를 구하는 플로이드 워셜 알고리즘을 사용하자. 플로이드 워셜 알고리즘은 링크를 참고하자.

 

 플로이드 워셜을 사용하여 모든 지점에서 다른 지점까지의 최단 거리를 구한 후  for문을 통해서 1번부터 N번까지를 시작지점으로하여 수색범위내에 도착 가능한 지점의 아이템 개수를 카운트한다. 이중 가장 큰 값을 찾으면 된다.

 

코드

import sys
input = sys.stdin.readline
INF = float('inf')

if __name__ == '__main__':
    N, M, R = map(int, input().split())  # 지역 개수, 수색범위, 길의 개수
    items = [0] + list(map(int, input().split()))  # 각 구역 아이템 개수
    roads = [[INF for _ in range(N+1)] for _ in range(N+1)]  # 길 정보

    for i in range(1, N+1):  # 자기 자신으로 가는 길은 0으로 초기화한다.
        roads[i][i] = 0

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

    # 플로이드 워셜 알고리즘 수행
    for k in range(N):
        for i in range(1, N+1):
            for j in range(1, N+1):
                roads[i][j] = min(roads[i][j], roads[i][k] + roads[k][j])

    res = 0
    for i in range(1, N+1):
        count = 0  # i번을 시작점으로 했을 때 수색할 수 있는 지점의 아이템 개수의 합

        for j in range(1, N+1):
            if roads[i][j] <= M:
                count += items[j]

        res = max(res, count)

    print(res)