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

💡문제접근

• 문제 그대로 구현하는 과정에서 IndexError가 자주 발생했던 문제

💡코드(메모리 : 31256KB, 시간 : 404ms)

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

n, m, r = map(int, input().strip().split())
graph = [[INF] * n for _ in range(n)]

items = list(map(int, input().strip().split()))
# 각 지역은 일정한 길이의 길로 다른 지역과 연결되어 있는데 이 길은 양방향 통행이 가능
for _ in range(r):
    a, b, I = map(int, input().strip().split())
    graph[a-1][b-1] = I
    graph[b-1][a-1] = I

# 자기 자신에서 자기 자신으로 가는 경우는 0
for a in range(n):
    for b in range(n):
        if a == b:
            graph[a][b] = 0

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

result = 0
for i in range(n):
    temp = 0
    for j in range(n):
        if graph[i][j] <= m:
            temp += items[j]
    result = max(result, temp)
print(result)

💡소요시간 : 27m