結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー ciffelia
提出日時 2025-04-20 15:40:28
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
AC  
実行時間 2,442 ms / 5,000 ms
コード長 1,324 bytes
コンパイル時間 435 ms
コンパイル使用メモリ 12,416 KB
実行使用メモリ 88,248 KB
最終ジャッジ日時 2025-04-20 15:41:23
合計ジャッジ時間 51,227 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq

def solve():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    N = int(data[0])
    M = int(data[1])
    K = int(data[2])
    C = list(map(int, data[3:3 + M]))
    uv = data[3 + M:]
    
    graph = [[] for _ in range(N+1)]
    for i in range(M):
        u = int(uv[2*i])
        v = int(uv[2*i+1])
        cost = C[i]
        graph[u].append((v, cost))
        graph[v].append((u, cost))

    # dist[町][使用済みクーポン数] = 最小コスト
    INF = 10**18
    dist = [[INF] * (K+1) for _ in range(N+1)]
    dist[1][0] = 0
    hq = []
    heapq.heappush(hq, (0, 1, 0))  # (今のコスト, 町, 使ったクーポン枚数)

    while hq:
        cost, u, used = heapq.heappop(hq)
        if dist[u][used] < cost:
            continue
        for v, edge_cost in graph[u]:
            # クーポンを使わない
            if dist[v][used] > cost + edge_cost:
                dist[v][used] = cost + edge_cost
                heapq.heappush(hq, (dist[v][used], v, used))
            # クーポンを使う
            if used < K and dist[v][used+1] > cost:
                dist[v][used+1] = cost
                heapq.heappush(hq, (dist[v][used+1], v, used+1))
    
    ans = min(dist[N])
    print(ans if ans < INF else -1)

if __name__ == "__main__":
    solve()
0