結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー YHz_ikiriAbu
提出日時 2025-04-19 00:26:19
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 1,703 bytes
コンパイル時間 346 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 47,632 KB
最終ジャッジ日時 2025-04-19 00:26:33
合計ジャッジ時間 13,927 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other TLE * 1 -- * 69
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
import math

INF = math.inf
n, m, k = map(int, input().split())
c = list(map(int, input().split()))
bridge = []
for i in range(m):
    u, v = map(int, input().split())
    bridge.append([u, v])


def dijkstra(
    start,
):  # 街1から街Nに最小の経費で向かいたい、K枚のクーポンを使うことができる
    dist = [[INF] * (k + 1) for _ in range(n + 1)]
    dist[start][0] = 0
    que = []
    heapq.heappush(que, (0, start, 0))  # (cost,now,クーポンの枚数)
    while que:
        cost, now, coupon = heapq.heappop(que)
        if dist[now][coupon] < cost:
            continue
        for i in range(m):
            u, v = bridge[i]
            if u == now:
                if dist[v][coupon] < cost + c[i]:
                    continue
                if coupon < k and dist[v][coupon + 1] > cost:
                    dist[v][coupon + 1] = cost
                    heapq.heappush(que, (cost, v, coupon + 1))
                if dist[v][coupon] > cost + c[i]:
                    dist[v][coupon] = cost + c[i]
                    heapq.heappush(que, (cost + c[i], v, coupon))
            elif v == now:
                if dist[u][coupon] < cost + c[i]:
                    continue
                if coupon < k and dist[u][coupon + 1] > cost:
                    dist[u][coupon + 1] = cost
                    heapq.heappush(que, (cost, u, coupon + 1))
                if dist[u][coupon] > cost + c[i]:
                    dist[u][coupon] = cost + c[i]
                    heapq.heappush(que, (cost + c[i], u, coupon))
    return dist[n][k]  # 街Nに到達するための最小の経費


ans = dijkstra(1)
if ans == INF:
    print(-1)
else:
    print(ans)
0