結果

問題 No.3111 Toll Optimization
ユーザー ponjuice
提出日時 2025-04-13 00:57:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 228 ms / 5,000 ms
コード長 1,879 bytes
コンパイル時間 3,231 ms
コンパイル使用メモリ 288,356 KB
実行使用メモリ 15,032 KB
最終ジャッジ日時 2025-04-15 10:06:18
合計ジャッジ時間 12,318 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, a, b) for(int i = a; i < (b); i++)
constexpr ll INF = 1'000'000'000'000'000'000;

int main(){
    // 入力
    int n,m,k;
    cin >> n >> m >> k;
    vector<int> c(m);
    rep(i, 0, m) cin >> c[i];
    vector<vector<array<int,2>>> graph(n);
    rep(i, 0, m) {
        int u, v;
        cin >> u >> v;
        u--,v--;
        graph[u].push_back({v, c[i]});
        graph[v].push_back({u, c[i]});
    }

    // dist[i][j]: クーポンをi枚使った時の町j+1までの最低料金
    vector<vector<ll>> dist(k+1, vector<ll>(n, INF));

    // ダイクストラ法を用いてそれぞれの最低料金を計算していく
    dist[0][0] = 0;
    using S = array<ll, 3>; // {最低料金, 使ったクーポンの数, 町の番号}
    priority_queue<S, vector<S>, greater<S>> pq; 
    pq.push({0, 0, 0});

    while(!pq.empty()){
        auto [now_cost, coupon, pos] = pq.top();
        pq.pop();
        if(now_cost != dist[coupon][pos]) continue;
        for(auto [to, edge_cost]: graph[pos]) {
            // クーポンを使用しない移動
            if(dist[coupon][to] > now_cost + edge_cost) {
                dist[coupon][to] = now_cost + edge_cost;
                pq.push({dist[coupon][to], coupon, to});
            }

            // クーポンを使用する移動
            if(coupon != k) {
                if(dist[coupon + 1][to] > now_cost) {
                    dist[coupon + 1][to] = now_cost;
                    pq.push({dist[coupon + 1][to], coupon + 1, to});
                }
            }
        }
    }

    // N にいく方法のうち、料金が最小のものを求める
    ll ans = INF;
    rep(i, 0, k+1) {
        ans = min(ans, dist[i][n-1]);
    }

    // 答えの出力
    if(ans != INF) cout << ans << endl;
    else cout << -1 << endl;
}
0