BOJ - 1602 - 도망자 원숭이

import sys

def solution():
    _INF = 1e9
    N, M, Q = map(int, sys.stdin.readline().split())
    dog = list(map(int, sys.stdin.readline().split()))
    maps = [[_INF for _ in range(N)] for _ in range(N)]
    penalty = [[_INF for _ in range(N)] for _ in range(N)]
    for i in range(N):
        maps[i][i] = 0
        penalty[i][i] = dog[i]

    for _ in range(M):
        a, b, distance = map(int, sys.stdin.readline().split())
        a, b = a-1, b-1

        maps[a][b] = distance
        maps[b][a] = distance

        penalty[a][b] = distance + max(dog[a], dog[b])
        penalty[b][a] = distance + max(dog[b], dog[a])

    dogArr = []
    for idx in range(len(dog)):
        dogArr.append([idx, dog[idx]])

    dogArr.sort(key=lambda x:x[1])

    for k in range(N):
        idx = dogArr[k][0]
        for i in range(N):
            for j in range(N):
                if i == j: continue
                maps[i][j] = min(maps[i][idx] + maps[idx][j], maps[i][j])
                penalty[i][j] = min(
                    penalty[i][j],
                    maps[i][j] + max(dog[i], max(dog[idx], dog[j]))
                )

    for _ in range(Q):
        S, T = map(int, sys.stdin.readline().split())
        S, T = S-1, T-1
        print(-1 if penalty[S][T] == _INF else penalty[S][T])

solution()

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