BOJ - 13907 - 세금

import sys

_INF = 1e9

def Dijkstra(Start, V, graph, matrix):
    matrix[Start][0] = 0

    for y in range(V):
        for x in range(V+1):
            if matrix[x][y] == _INF: continue
            for l, w in graph[x]:
                matrix[l][y+1] = min(matrix[l][y+1], matrix[x][y] + w)

def solution():
    N, M, K = map(int, sys.stdin.readline().split())
    S, D = map(int, sys.stdin.readline().split())
    graph = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b, w = map(int, sys.stdin.readline().split())
        graph[a].append([b, w])
        graph[b].append([a, w])

    matrix = [[_INF for _ in range(N+1)] for _ in range(N+1)]
    Dijkstra(S, N, graph, matrix)

    print(min(matrix[D]))
    for _ in range(K):
        p = int(sys.stdin.readline())
        for i in range(N+1):
            matrix[D][i] += i * p
        print(min(matrix[D]))


solution()

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