結果

問題 No.3111 Toll Optimization
ユーザー 37zigen
提出日時 2025-04-19 14:45:47
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 352 ms / 5,000 ms
コード長 1,831 bytes
コンパイル時間 2,436 ms
コンパイル使用メモリ 212,912 KB
実行使用メモリ 20,548 KB
最終ジャッジ日時 2025-04-19 14:46:02
合計ジャッジ時間 14,563 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 70
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const ll INF = 1e18;

int main() {
    // 入力
    int N, M, K;
    cin >> N >> M >> K;
    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];
        u[i]--; v[i]--; // 0-based indexing
    }

    // グラフ構築（隣接リスト）
    vector<vector<pair<int, ll>>> adj(N);
    for (int i = 0; i < M; i++) {
        adj[u[i]].push_back({v[i], C[i]});
        adj[v[i]].push_back({u[i], C[i]});
    }

    // ダイクストラ法
    vector<vector<ll>> dist(N, vector<ll>(K + 1, INF));
    dist[0][0] = 0; // 町1（0-based）でクーポン0枚
    priority_queue<tuple<ll, int, int>, vector<tuple<ll, int, int>>, greater<>> pq;
    pq.push({0, 0, 0}); // {コスト, 町, クーポン枚数}

    while (!pq.empty()) {
        auto [cost, v, k] = pq.top();
        pq.pop();

        // 既により良い経路がある場合スキップ
        if (cost > dist[v][k]) continue;

        // 隣接する町を探索
        for (auto [u, c] : adj[v]) {
            // クーポンを使わない
            if (dist[u][k] > cost + c) {
                dist[u][k] = cost + c;
                pq.push({dist[u][k], u, k});
            }
            // クーポンを使う（k < K のとき）
            if (k < K && dist[u][k + 1] > cost) {
                dist[u][k + 1] = cost;
                pq.push({dist[u][k + 1], u, k + 1});
            }
        }
    }

    // 町Nの最小コストを計算
    ll ans = INF;
    for (int k = 0; k <= K; k++) {
        ans = min(ans, dist[N - 1][k]);
    }

    // 出力
    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}
0