結果

問題 No.3111 Toll Optimization
ユーザー 入野拳樹
提出日時 2025-04-19 23:58:57
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 247 ms / 5,000 ms
コード長 1,702 bytes
コンパイル時間 1,285 ms
コンパイル使用メモリ 90,784 KB
実行使用メモリ 20,528 KB
最終ジャッジ日時 2025-04-19 23:59:11
合計ジャッジ時間 11,594 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <limits>

using namespace std;
using ll = long long;
const ll INF = 1LL << 60;

struct Edge {
    int to;
    ll cost;
};

int main() {
    int N, M, K;
    cin >> N >> M >> K;

    vector<Edge> graph[N + 1];
    vector<ll> C(M);
    vector<int> u(M), v(M);

    for (int i = 0; i < M; ++i) {
        cin >> C[i];
    }
    for (int i = 0; i < M; ++i) {
        cin >> u[i] >> v[i];
        graph[u[i]].push_back({v[i], C[i]});
        graph[v[i]].push_back({u[i], C[i]});
    }

    // dist[node][used_coupons] = min cost to reach 'node' using 'used_coupons'
    vector<vector<ll>> dist(N + 1, vector<ll>(K + 1, INF));
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;

    dist[1][0] = 0;
    pq.push({0, 1, 0}); // {cost, node, used_coupons}

    while (!pq.empty()) {
        auto [cur_cost, node, used] = pq.top();
        pq.pop();

        if (cur_cost > dist[node][used]) continue;

        for (const auto& e : graph[node]) {
            // クーポンを使わない
            if (dist[e.to][used] > cur_cost + e.cost) {
                dist[e.to][used] = cur_cost + e.cost;
                pq.push({dist[e.to][used], e.to, used});
            }
            // クーポンを使う
            if (used < K && dist[e.to][used + 1] > cur_cost) {
                dist[e.to][used + 1] = cur_cost;
                pq.push({dist[e.to][used + 1], e.to, used + 1});
            }
        }
    }

    ll ans = INF;
    for (int k = 0; k <= K; ++k) {
        ans = min(ans, dist[N][k]);
    }

    if (ans == INF) cout << -1 << endl;
    else cout << ans << endl;

    return 0;
}
0