結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー hato336
提出日時 2025-04-18 21:05:48
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,010 ms / 5,000 ms
コード長 878 bytes
コンパイル時間 294 ms
コンパイル使用メモリ 82,196 KB
実行使用メモリ 131,328 KB
最終ジャッジ日時 2025-04-18 21:06:36
合計ジャッジ時間 46,448 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

n,m,k = map(int,input().split())
c = list(map(int,input().split()))
edge = [[] for i in range(n)]
for i in range(m):
    u,v = map(int,input().split())
    u-=1
    v-=1
    edge[u].append((v,c[i]))
    edge[v].append((u,c[i]))
dist = [[1<<60 for i in range(n)] for j in range(k+1)]
start = 0
d = []

import heapq
heapq.heappush(d,(0,0,0))
dist[start][0] = 0
while d:
    _,cnt,now = heapq.heappop(d)
    if _ > dist[cnt][now]:
        continue
    for to,cost in edge[now]:
        if dist[cnt][to] > dist[cnt][now] + cost:
            dist[cnt][to] = dist[cnt][now] + cost
            heapq.heappush(d,(dist[cnt][to],cnt,to))
        if cnt + 1 <= k and dist[cnt+1][to] > dist[cnt][now] + 0:
            dist[cnt+1][to] = dist[cnt][now] + 0
            heapq.heappush(d,(dist[cnt+1][to],cnt+1,to))
ans = min(dist[i][-1] for i in range(k+1))
print(ans if ans < (1<<60) else -1)
0