結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー Nzt3
提出日時 2025-04-15 11:31:20
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,968 ms / 5,000 ms
コード長 957 bytes
コンパイル時間 395 ms
コンパイル使用メモリ 82,088 KB
実行使用メモリ 138,392 KB
最終ジャッジ日時 2025-04-15 11:32:09
合計ジャッジ時間 43,144 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

n,m,k = map(int, input().split())
c = list(map(int, input().split()))
graph = [[] for _ in range(n)]

for i in range(m):
    u,v = map(int, input().split())
    graph[u-1].append((v-1, c[i]))
    graph[v-1].append((u-1, c[i]))

start = 0
end = n-1

dist = [[10**17] * (k + 1) for _ in range(n)]

dist[start][0] = 0

queue = [(0, start, 0)]

while queue:
    now_cost, now_pos, coupon = heapq.heappop(queue)

    if dist[now_pos][coupon] < now_cost:
        continue

    for to, edge_cost in graph[now_pos]:
        if coupon < k:
            if dist[to][coupon + 1] > now_cost:
                dist[to][coupon + 1] = now_cost
                heapq.heappush(queue, (now_cost, to, coupon + 1))

        if dist[to][coupon] > now_cost + edge_cost:
            dist[to][coupon] = now_cost + edge_cost
            heapq.heappush(queue, (now_cost + edge_cost, to, coupon))

ans = min(dist[end])

if ans == 10**17:
    print(-1)
else:
    print(ans)
0