結果

問題 No.1442 I-wate Shortest Path Problem
コンテスト
ユーザー lam6er
提出日時 2025-03-31 17:54:03
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 5,327 bytes
コンパイル時間 6,974 ms
コンパイル使用メモリ 228,152 KB
実行使用メモリ 39,476 KB
最終ジャッジ日時 2025-03-31 17:55:45
合計ジャッジ時間 15,853 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 12 WA * 13
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

typedef long long ll;
const ll INF = 1e18;

struct LCA {
    vector<int> depth;
    vector<vector<int>> parent;
    vector<vector<ll>> dist;
    int max_log;

    LCA(int n, const vector<vector<pair<int, ll>>> &tree) {
        max_log = 0;
        while ((1 << max_log) < n) max_log++;
        depth.resize(n);
        parent.assign(max_log, vector<int>(n, -1));
        dist.assign(max_log, vector<ll>(n, 0));

        queue<int> q;
        q.push(0);
        depth[0] = 0;
        parent[0][0] = -1;
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (auto &[v, c] : tree[u]) {
                if (parent[0][v] == -1 && v != 0) {
                    depth[v] = depth[u] + 1;
                    parent[0][v] = u;
                    dist[0][v] = c;
                    q.push(v);
                }
            }
        }

        for (int k = 1; k < max_log; k++) {
            for (int v = 0; v < n; v++) {
                if (parent[k-1][v] != -1) {
                    parent[k][v] = parent[k-1][parent[k-1][v]];
                    dist[k][v] = dist[k-1][v] + dist[k-1][parent[k-1][v]];
                }
            }
        }
    }

    pair<int, ll> lca(int u, int v) {
        ll sum = 0;
        if (depth[u] < depth[v]) swap(u, v);
        for (int k = max_log-1; k >= 0; k--) {
            if (depth[u] - (1 << k) >= depth[v]) {
                sum += dist[k][u];
                u = parent[k][u];
            }
        }
        if (u == v) return {u, sum};
        for (int k = max_log-1; k >= 0; k--) {
            if (parent[k][u] != -1 && parent[k][u] != parent[k][v]) {
                sum += dist[k][u] + dist[k][v];
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        sum += dist[0][u] + dist[0][v];
        return {parent[0][u], sum};
    }

    ll distance(int u, int v) {
        auto [ancestor, d] = lca(u, v);
        return d;
    }
};

vector<ll> dijkstra_airline(const vector<vector<pair<int, ll>>> &tree, const vector<int> &sources) {
    int n = tree.size();
    vector<ll> dist(n, INF);
    priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;

    for (int s : sources) {
        dist[s] = 0;
        pq.emplace(0, s);
    }

    while (!pq.empty()) {
        auto [d, u] = pq.top();
        pq.pop();

        if (d > dist[u]) continue;

        for (auto [v, c] : tree[u]) {
            if (dist[v] > dist[u] + c) {
                dist[v] = dist[u] + c;
                pq.emplace(dist[v], v);
            }
        }
    }

    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;

    vector<vector<pair<int, ll>>> tree(N);
    for (int i = 0; i < N-1; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        tree[a].emplace_back(b, c);
        tree[b].emplace_back(a, c);
    }

    LCA lca(N, tree);

    vector<int> P(K);
    vector<vector<ll>> min_dist(K);
    for (int i = 0; i < K; i++) {
        int M, p;
        cin >> M >> p;
        P[i] = p;
        vector<int> sources;
        for (int j = 0; j < M; j++) {
            int x;
            cin >> x;
            x--;
            sources.push_back(x);
        }
        min_dist[i] = dijkstra_airline(tree, sources);
    }

    vector<ll> sum_P(1 << K, 0);
    for (int mask = 1; mask < (1 << K); mask++) {
        for (int i = 0; i < K; i++) {
            if (mask & (1 << i)) {
                sum_P[mask] = sum_P[mask ^ (1 << i)] + P[i];
                break;
            }
        }
    }

    int Q;
    cin >> Q;

    vector<int> sorted_a_order(K), sorted_b_order(K);
    while (Q--) {
        int u, v;
        cin >> u >> v;
        u--; v--;

        ll rail_cost = lca.distance(u, v);

        if (K == 0) {
            cout << rail_cost << '\n';
            continue;
        }

        vector<ll> a(K), b(K);
        for (int i = 0; i < K; i++) {
            a[i] = min_dist[i][u];
            b[i] = min_dist[i][v];
        }

        iota(sorted_a_order.begin(), sorted_a_order.end(), 0);
        sort(sorted_a_order.begin(), sorted_a_order.end(), [&a](int i, int j) { return a[i] < a[j]; });

        iota(sorted_b_order.begin(), sorted_b_order.end(), 0);
        sort(sorted_b_order.begin(), sorted_b_order.end(), [&b](int i, int j) { return b[i] < b[j]; });

        ll min_candidate = INF;

        for (int mask = 1; mask < (1 << K); mask++) {
            ll sum_p = sum_P[mask];

            ll current_a = INF;
            for (int i : sorted_a_order) {
                if (mask & (1 << i)) {
                    current_a = a[i];
                    break;
                }
            }

            ll current_b = INF;
            for (int i : sorted_b_order) {
                if (mask & (1 << i)) {
                    current_b = b[i];
                    break;
                }
            }

            if (current_a == INF || current_b == INF) continue;

            ll candidate = sum_p + current_a + current_b;
            if (candidate < min_candidate) {
                min_candidate = candidate;
            }
        }

        ll answer = min(rail_cost, min_candidate);
        cout << answer << '\n';
    }

    return 0;
}
0