結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー norioc
提出日時 2025-04-22 06:19:55
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,582 ms / 5,000 ms
コード長 760 bytes
コンパイル時間 445 ms
コンパイル使用メモリ 82,416 KB
実行使用メモリ 169,928 KB
最終ジャッジ日時 2025-04-22 06:21:09
合計ジャッジ時間 69,401 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop
from collections import defaultdict

INF = 1 << 60
N, M, K = map(int, input().split())
C = list(map(int, input().split()))
adj = defaultdict(list)
for i in range(M):
    u, v = map(lambda x: int(x)-1, input().split())
    adj[u].append((v, C[i]))
    adj[v].append((u, C[i]))

dists = [[INF] * N for _ in range(K+1)]
q = [(0, 0, 0)]
while q:
    cost, k, v = heappop(q)
    if dists[k][v] <= cost: continue
    dists[k][v] = cost

    for to, w in adj[v]:
        c = cost + w
        if c < dists[k][to]:
            heappush(q, (c, k, to))

        if k < K and cost < dists[k+1][to]:
            heappush(q, (cost, k+1, to))

ans = min(dists[k][N-1] for k in range(K+1))
if ans == INF:
    print(-1)
else:
    print(ans)
0