結果

問題 No.3111 Toll Optimization
ユーザー stderr0r
提出日時 2025-04-18 21:25:46
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
WA  
実行時間 -
コード長 819 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 12,032 KB
実行使用メモリ 211,840 KB
最終ジャッジ日時 2025-04-18 21:27:51
合計ジャッジ時間 108,575 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 66 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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))

ans = dijkstra(g, n*4+10, 0)[n*k+n-1]
print(ans if ans != INF else -1)
0