結果
問題 |
No.3111 Toll Optimization
|
ユーザー |
![]() |
提出日時 | 2025-04-18 20:30:30 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,209 ms / 5,000 ms |
コード長 | 1,007 bytes |
コンパイル時間 | 345 ms |
コンパイル使用メモリ | 82,356 KB |
実行使用メモリ | 145,400 KB |
最終ジャッジ日時 | 2025-04-18 20:31:32 |
合計ジャッジ時間 | 45,662 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 70 |
ソースコード
from heapq import heappush, heappop N, M, K = map(int, input().split()) C = list(map(int, input().split())) G = [[] for _ in range(N)] for i in range(M): u, v = map(int, input().split()) G[u-1].append((v-1, C[i])) G[v-1].append((u-1, C[i])) INF = 10**18 def dijkstra(start): dist = [[INF]*(K+1) for _ in range(N)] dist[start][0] = 0 visited = [[False]*(K+1) for _ in range(N)] que = [(0, start, 0)] while que: d, now, c = heappop(que) if visited[now][c]: continue visited[now][c] = True for next, weight in G[now]: if dist[now][c]+weight < dist[next][c]: dist[next][c] = dist[now][c]+weight heappush(que, (dist[next][c], next, c)) if c < K and dist[now][c] < dist[next][c+1]: dist[next][c+1] = dist[now][c] heappush(que, (dist[next][c+1], next, c+1)) return dist dist = dijkstra(0) ans = min(dist[-1]) print(ans if ans != INF else -1)