結果

問題 No.3111 Toll Optimization
ユーザー stderr0r
提出日時 2025-04-18 21:32:01
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 4,331 ms / 5,000 ms
コード長 855 bytes
コンパイル時間 109 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 211,992 KB
最終ジャッジ日時 2025-04-18 21:33:52
合計ジャッジ時間 110,593 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop, heappush
INF = float("inf")

def dijkstra(graph, n, s):
    d = [INF] * n
    d[s] = 0
    q = [(0, s)]
    while q:
        dist, v = heappop(q)
        if d[v] < dist: continue
        for nv, cost in graph[v]:
            if d[nv] > d[v] + cost:
                d[nv] = d[v] + cost
                heappush(q, (d[nv], nv))
    return d

n, m, k = map(int, input().split())
c = list(map(int, input().split()))
g = [[] for _ in range(n*4+10)]
for i in range(m):
    u, v = map(lambda x: int(x)-1, input().split())
    for j in range(k+1):
        g[n*j+u].append((n*j+v, c[i]))
        g[n*j+v].append((n*j+u, c[i]))
    for j in range(k):
        g[n*j+u].append((n*(j+1)+v, 0))
        g[n*j+v].append((n*(j+1)+u, 0))

res = dijkstra(g, n*4+10, 0)
ans = min(res[n*j+n-1] for j in range(k+1))
print(ans if ans != INF else -1)
0