結果

問題 No.3111 Toll Optimization
ユーザー Naru820
提出日時 2025-03-22 18:18:35
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 2,962 ms / 5,000 ms
コード長 1,175 bytes
コンパイル時間 338 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 211,112 KB
最終ジャッジ日時 2025-04-15 10:07:01
合計ジャッジ時間 70,493 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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