結果

問題 No.1442 I-wate Shortest Path Problem
ユーザー KoDKoD
提出日時 2021-03-27 11:27:26
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 511 ms / 3,000 ms
コード長 5,187 bytes
コンパイル時間 2,548 ms
コンパイル使用メモリ 222,864 KB
実行使用メモリ 47,212 KB
最終ジャッジ日時 2024-11-29 08:12:17
合計ジャッジ時間 10,110 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 3 ms
5,248 KB
testcase_02 AC 10 ms
5,248 KB
testcase_03 AC 38 ms
5,248 KB
testcase_04 AC 9 ms
5,248 KB
testcase_05 AC 8 ms
5,248 KB
testcase_06 AC 37 ms
5,248 KB
testcase_07 AC 7 ms
5,248 KB
testcase_08 AC 39 ms
5,248 KB
testcase_09 AC 15 ms
5,376 KB
testcase_10 AC 40 ms
5,248 KB
testcase_11 AC 41 ms
5,248 KB
testcase_12 AC 343 ms
40,320 KB
testcase_13 AC 167 ms
33,024 KB
testcase_14 AC 254 ms
36,692 KB
testcase_15 AC 234 ms
35,428 KB
testcase_16 AC 311 ms
37,968 KB
testcase_17 AC 507 ms
42,360 KB
testcase_18 AC 511 ms
42,640 KB
testcase_19 AC 372 ms
40,132 KB
testcase_20 AC 495 ms
42,500 KB
testcase_21 AC 503 ms
42,488 KB
testcase_22 AC 188 ms
39,040 KB
testcase_23 AC 399 ms
47,212 KB
testcase_24 AC 148 ms
32,832 KB
testcase_25 AC 350 ms
39,272 KB
testcase_26 AC 157 ms
37,680 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using i32 = std::int32_t;
using u32 = std::uint32_t;
using i64 = std::int64_t;
using u64 = std::uint64_t;
using i128 = __int128_t;
using u128 = __uint128_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

class rep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept: itr(pos) { }
        constexpr void operator ++ () noexcept { ++itr; }
        constexpr bool operator != (const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator * () const noexcept { return itr; }
    };
    const Iter first, last;
public:
    explicit constexpr rep(const usize first, const usize last) noexcept: first(first), last(std::max(first, last)) { }
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T, T Div = 2>
constexpr T INFTY = std::numeric_limits<T>::max() / Div;

template <class T>
bool setmin(T& lhs, const T& rhs) {
    if (lhs > rhs) {
        lhs = rhs;
        return true;
    }
    return false;
}

template <class F>
struct RecLambda: private F {
    explicit constexpr RecLambda(F&& f): F(std::forward<F>(f)) { }
    template <class... Args>
    constexpr decltype(auto) operator () (Args&&... args) const {
        return F::operator()(*this, std::forward<Args>(args)...);
    }
};

class revrep {
    struct Iter {
        usize itr;
        constexpr Iter(const usize pos) noexcept: itr(pos) { }
        constexpr void operator ++ () noexcept { --itr; }
        constexpr bool operator != (const Iter& other) const noexcept { return itr != other.itr; }
        constexpr usize operator * () const noexcept { return itr; }
    };
    const Iter first, last;
public:
    explicit constexpr revrep(const usize first, const usize last) noexcept: first(last - 1), last(std::min(first, last) - 1) { }
    constexpr Iter begin() const noexcept { return first; }
    constexpr Iter end() const noexcept { return last; }
};

template <class T>
using Vec = std::vector<T>;

template <class T>
using Heap = std::priority_queue<T, Vec<T>, std::greater<T>>;

void E_main() {
    usize N, K;
    std::cin >> N >> K;
    Vec<Vec<std::pair<usize, u32>>> tree(N), graph(N + K);
    for (auto i: rep(1, N)) {
        usize a, b;
        u32 c;
        std::cin >> a >> b >> c;
        a -= 1;
        b -= 1;
        tree[a].emplace_back(b, c);
        tree[b].emplace_back(a, c);
        graph[a].emplace_back(b, c);
        graph[b].emplace_back(a, c);
    }
    Vec<u32> P(K);
    for (auto i: rep(0, K)) {
        usize m;
        std::cin >> m >> P[i];
        while (m--) {
            usize u;
            std::cin >> u;
            u -= 1;
            graph[u].emplace_back(N + i, P[i]);
            graph[N + i].emplace_back(u, 0);
        }
    }
    const auto dijkstra = [&](const usize src) {
        Vec<u64> dist(N + K, INFTY<u64>);
        Heap<std::pair<u64, usize>> que;
        const auto push = [&](const usize u, const u64 d) {
            if (setmin(dist[u], d)) {
                que.emplace(d, u);
            }
        };
        push(src, 0);
        while (!que.empty()) {
            const auto [d, u] = que.top();
            que.pop();
            if (dist[u] < d) {
                continue;
            }
            for (const auto [v, c]: graph[u]) {
                push(v, d + c);
            }
        }
        return dist;
    };
    Vec<Vec<u64>> dist(K);
    for (auto i: rep(0, K)) {
        dist[i] = dijkstra(N + i);
    }
    Vec<usize> parent(N), depth(N);
    Vec<u64> length(N);
    RecLambda([&](auto &&dfs, const usize u, const usize p, const usize d, const u64 l) -> void {
        parent[u] = p;
        depth[u] = d;
        length[u] = l;
        for (const auto [v, c]: tree[u]) {
            if (v != p) {
                dfs(v, u, d + 1, l + c);
            }
        }
    })(0, 0, 0, 0); 
    std::array<Vec<usize>, 17> lift;
    lift[0] = parent;
    for (auto i: rep(0, 16)) {
        lift[i + 1].resize(N);
        for (auto j: rep(0, N)) {
            lift[i + 1][j] = lift[i][lift[i][j]];
        }
    } 
    const auto lca = [&](usize u, usize v) {
        if (depth[u] < depth[v]) {
            std::swap(u, v);
        }
        const auto dif = depth[u] - depth[v];
        for (auto i: rep(0, 17)) {
            if (dif >> i & 1) {
                u = lift[i][u];
            }
        }
        if (u == v) {
            return u;
        }
        for (auto i: revrep(0, 17)) {
            if (lift[i][u] != lift[i][v]) {
                u = lift[i][u];
                v = lift[i][v];
            }
        }
        return parent[u];
    };
    usize Q;
    std::cin >> Q;
    while (Q--) {
        usize u, v;
        std::cin >> u >> v;
        u -= 1;
        v -= 1;
        const auto c = lca(u, v);
        u64 ans = length[u] + length[v] - 2 * length[c];
        for (auto i: rep(0, K)) {
            setmin(ans, dist[i][u] + dist[i][v] + P[i]);
        }
        std::cout << ans << '\n';
    }
    return;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    E_main();
    return 0;
}
0