結果

問題 No.3111 Toll Optimization
ユーザー ponjuice
提出日時 2025-04-13 01:19:07
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,870 bytes
コンパイル時間 3,835 ms
コンパイル使用メモリ 290,680 KB
実行使用メモリ 14,876 KB
最終ジャッジ日時 2025-04-15 10:06:45
合計ジャッジ時間 13,599 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 66 WA * 4
権限があれば一括ダウンロードができます

ソースコード

diff # 

// waのコード
#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 = dist[k][n-1];

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