結果

問題 No.3111 Toll Optimization
ユーザー Daniel Agatan
提出日時 2025-04-20 01:59:56
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,235 bytes
コンパイル時間 2,820 ms
コンパイル使用メモリ 216,412 KB
実行使用メモリ 29,772 KB
最終ジャッジ日時 2025-04-20 02:00:14
合計ジャッジ時間 17,071 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other WA * 5 TLE * 1 -- * 64
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

struct Data {
    int value, u, used;
    bool operator>(const Data& other) const {
        return value > other.value;
    }
};

struct pair_hash {
    template <class T1, class T2>
    size_t operator ( ) (const pair<T1, T2>& p) const {
        auto h1 = hash<T1>{}(p.first);
        auto h2 = hash<T2>{}(p.second);
        return h1 ^ h2;  // Combine the two hashes
    }
};

void solve() {
    int n, m, k;
    cin >> n >> m >> k;

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

    unordered_map<int, vector<pair<int, int>>> edges;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        edges[u].emplace_back(v, values[i]);
        edges[v].emplace_back(u, values[i]);
    }

    unordered_map<pair<int, int>, int, pair_hash> memo;
    memo[{1, 0}] = 0;

    priority_queue<Data, vector<Data>, greater<Data>> minHeap;
    minHeap.push({0, 1, 0});

    while (!minHeap.empty()) {
        Data current = minHeap.top();
        minHeap.pop();
        int value = current.value;
        int u = current.u;
        int used = current.used;

        for (const auto& e : edges[u]) {
            int v = e.first;
            int cost = e.second;

            if (used < k) {
                pair<int, int> key = {v, used + 1};
                if (memo.find(key) == memo.end() || value < memo[key]) {
                    memo[key] = value;
                    minHeap.push({value, v, used + 1});
                }
            }

            pair<int, int> key = {v, used};
            if (memo.find(key) == memo.end() || value + cost < memo[key]) {
                memo[key] = value + cost;
                minHeap.push({value + cost, v, used});
            }
        }
    }

    int result = INT_MAX;
    for (int i = 0; i <= k; i++) {
        pair<int, int> key = {n, i};
        if (memo.find(key) != memo.end()) {
            result = min(result, memo[key]);
        }
    }

    if (result == INT_MAX) {
        result = -1;
    }

    cout << result << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int tc = 1;
    while (tc--) {
        solve();
    }
    return 0;
}
0