結果

問題 No.3111 Toll Optimization
コンテスト
ユーザー YHz_ikiriAbu
提出日時 2025-04-19 00:27:32
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 2,138 bytes
コンパイル時間 922 ms
コンパイル使用メモリ 91,308 KB
実行使用メモリ 8,064 KB
最終ジャッジ日時 2025-04-19 00:28:00
合計ジャッジ時間 23,063 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 2 -- * 66
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using namespace std;

const long long INF = numeric_limits<long long>::max();

int n, m, k;
vector<int> c;
vector<pair<int, int>> bridge;

long long dijkstra(int start) {
    vector<vector<long long>> dist(n + 1, vector<long long>(k + 1, INF));
    dist[start][0] = 0;

    priority_queue<tuple<long long, int, int>, vector<tuple<long long, int, int>>, greater<>> que;
    que.push({0, start, 0}); // (cost, now, coupon)

    while (!que.empty()) {
        auto [cost, now, coupon] = que.top();
        que.pop();

        if (dist[now][coupon] < cost) {
            continue;
        }

        for (int i = 0; i < m; ++i) {
            int u = bridge[i].first;
            int v = bridge[i].second;

            if (u == now) {
                if (coupon < k && dist[v][coupon + 1] > cost) {
                    dist[v][coupon + 1] = cost;
                    que.push({cost, v, coupon + 1});
                }
                if (dist[v][coupon] > cost + c[i]) {
                    dist[v][coupon] = cost + c[i];
                    que.push({cost + c[i], v, coupon});
                }
            } else if (v == now) {
                if (coupon < k && dist[u][coupon + 1] > cost) {
                    dist[u][coupon + 1] = cost;
                    que.push({cost, u, coupon + 1});
                }
                if (dist[u][coupon] > cost + c[i]) {
                    dist[u][coupon] = cost + c[i];
                    que.push({cost + c[i], u, coupon});
                }
            }
        }
    }

    long long result = INF;
    for (int i = 0; i <= k; ++i) {
        result = min(result, dist[n][i]);
    }
    return result;
}

int main() {
    cin >> n >> m >> k;
    c.resize(m);
    bridge.resize(m);

    for (int i = 0; i < m; ++i) {
        cin >> c[i];
    }

    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        bridge[i] = {u, v};
    }

    long long ans = dijkstra(1);
    if (ans == INF) {
        cout << -1 << endl;
    } else {
        cout << ans << endl;
    }

    return 0;
}
0