[Python] 백준14938 서강그라운드

23 Jun 2023 in Study on Algorithm

백준14938 서강그라운드 링크

문제

예제 입력

---

코드

import sys
n, m, r = map(int, input().split())
arr = [0] + list(map(int, input().split()))
graph = [[float("inf")]*(n+1) for _ in range(n+1)]

for _ in range(r):
    v1, v2, val = map(int, sys.stdin.readline().split())
    graph[v1][v2] = val
    graph[v2][v1] = val

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

ans = 0
for i in range(1, n+1):
    tmp = 0
    for j in range(1, n+1):
        if graph[i][j] <= m:
            tmp += arr[j]
    if ans < tmp:
        ans = tmp
        
print(ans)

설명

파이썬을 통해서 사용자로부터 입력받아 플로이드-워셜 알고리즘을 사용하여 서강그라운드를 구현했습니다.

---

결과