結果

問題 No.3111 Toll Optimization
ユーザー Naru820
提出日時 2025-03-22 17:49:17
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 990 ms / 5,000 ms
コード長 1,175 bytes
コンパイル時間 629 ms
コンパイル使用メモリ 82,664 KB
実行使用メモリ 172,296 KB
最終ジャッジ日時 2025-04-15 10:05:56
合計ジャッジ時間 28,642 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import sys
import heapq

def dijkstra(start, graph, INF):
    n = len(graph)
    dist = [INF] * n
    dist[start] = 0
    hq = [(0, start)]
    while hq:
        d, now = heapq.heappop(hq)
        if dist[now] < d:
            continue
        for nxt, cost in graph[now]:
            if dist[nxt] > d + cost:
                dist[nxt] = d + cost
                heapq.heappush(hq, (dist[nxt], nxt))
    return dist

def main():
    input = sys.stdin.readline
    n, m, k = map(int, input().split())
    c = list(map(int, input().split()))
    graph = [[] for _ in range(n * (k + 1))]
    
    for i in range(m):
        u, v = map(int, input().split())
        u -= 1 
        v -= 1
        for j in range(k + 1):
            graph[n * j + u].append((n * j + v, c[i]))
            graph[n * j + v].append((n * j + u, c[i]))
            if j != k:
                graph[n * j + u].append((n * (j + 1) + v, 0))
                graph[n * j + v].append((n * (j + 1) + u, 0))
    
    INF = 2 * 10**18
    dist = dijkstra(0, graph, INF)
    
    ans = INF
    for j in range(k + 1):
        ans = min(ans, dist[n * j + (n - 1)])
    
    print(-1 if ans == INF else ans)

main()
0