#956440 (C++17(clang)) No.1602 With Animals into Institute 2

提出ソース

結果

問題	No.1602 With Animals into Institute 2
ユーザー	yanx
提出日時	2024-02-29 22:08:24
言語	C++17(clang) (17.0.6 + boost 1.83.0)
結果	AC
実行時間	446 ms / 4,000 ms
コード長	5,573 bytes
コンパイル時間	6,125 ms
コンパイル使用メモリ	139,592 KB
実行使用メモリ	26,168 KB
最終ジャッジ日時	2024-02-29 22:08:41
合計ジャッジ時間	16,396 ms
ジャッジサーバーID （参考情報）	judge11 / judge15

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,676 KB
testcase_01	AC	1 ms 6,676 KB
testcase_02	AC	2 ms 6,676 KB
testcase_03	AC	4 ms 6,676 KB
testcase_04	AC	5 ms 6,676 KB
testcase_05	AC	7 ms 6,676 KB
testcase_06	AC	229 ms 23,108 KB
testcase_07	AC	229 ms 23,124 KB
testcase_08	AC	399 ms 26,168 KB
testcase_09	AC	374 ms 25,372 KB
testcase_10	AC	426 ms 25,408 KB
testcase_11	AC	446 ms 25,404 KB
testcase_12	AC	368 ms 25,412 KB
testcase_13	AC	389 ms 25,424 KB
testcase_14	AC	364 ms 25,412 KB
testcase_15	AC	364 ms 25,400 KB
testcase_16	AC	391 ms 25,376 KB
testcase_17	AC	363 ms 25,404 KB
testcase_18	AC	5 ms 6,676 KB
testcase_19	AC	6 ms 6,676 KB
testcase_20	AC	5 ms 6,676 KB
testcase_21	AC	5 ms 6,676 KB
testcase_22	AC	5 ms 6,676 KB
testcase_23	AC	5 ms 6,676 KB
testcase_24	AC	6 ms 6,676 KB
testcase_25	AC	6 ms 6,676 KB
testcase_26	AC	6 ms 6,676 KB
testcase_27	AC	2 ms 6,676 KB
testcase_28	AC	1 ms 6,676 KB
testcase_29	AC	2 ms 6,676 KB
testcase_30	AC	2 ms 6,676 KB
testcase_31	AC	2 ms 6,676 KB
testcase_32	AC	1 ms 6,676 KB
testcase_33	AC	1 ms 6,676 KB
testcase_34	AC	2 ms 6,676 KB
testcase_35	AC	2 ms 6,676 KB
testcase_36	AC	1 ms 6,676 KB
testcase_37	AC	2 ms 6,676 KB
testcase_38	AC	2 ms 6,676 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

#include <cassert>
#include <queue>
#include <tuple>
#include <vector>

// CUT begin
// Single-source unorthodox shortest paths
// Complexity: O(M log M)
// This implementation is based on: https://gist.github.com/wata-orz/d3037bd0b919c76dd9ddc0379e1e3192
// Reference:
// [1] Y. Iwata and Y. Yamaguchi, "Finding a Shortest Non-zero Path in Group-Labeled Graphs,"
//     https://arxiv.org/abs/1906.04062
template <class T, T INF, class G> struct ShortestNonzeroPath {
    int V;
    std::vector<std::vector<std::tuple<int, T, G>>> to;
    ShortestNonzeroPath(int n) : V(n), to(n) { static_assert(INF > 0, "INF must be positive"); }
    void add_bi_edge(int u, int v, T len, G g) {
        assert(u >= 0 and u < V);
        assert(v >= 0 and v < V);
        assert(len >= 0);
        to[u].emplace_back(v, len, g);
        to[v].emplace_back(u, len, -g);
    }

private:
    std::vector<T> dist_sp;
    std::vector<int> parent_sp, depth_sp;
    std::vector<G> psi; // psi[path = v0v1...vn] = psi[v0v1] * psi[v1v2] * ... * psi[v(n - 1)vn]

    std::vector<int> uf_ps;
    int _find(int x) {
        if (uf_ps[x] == -1) {
            return x;
        } else {
            return uf_ps[x] = _find(uf_ps[x]);
        }
    }
    void _unite(int r, int c) { uf_ps[c] = r; }

public:
    int s;
    std::vector<T> dist; // dist[i] = Shortest distance of nonzero path from s to i
    void solve(int s_) {
        s = s_;
        assert(s >= 0 and s < V);

        // Solve SSSP
        {
            dist_sp.assign(V, INF);
            depth_sp.assign(V, -1), parent_sp.assign(V, -1);
            psi.assign(V, G());
            std::priority_queue<std::pair<T, int>, std::vector<std::pair<T, int>>,
                                std::greater<std::pair<T, int>>>
                que;
            dist_sp[s] = 0, depth_sp[s] = 0;
            que.emplace(0, s);
            while (que.size()) {
                T d, l;
                int u, v;
                G g;
                std::tie(d, u) = que.top();
                que.pop();
                if (dist_sp[u] != d) continue;
                for (const auto &p : to[u]) {
                    std::tie(v, l, g) = p;
                    const auto d2 = d + l;
                    if (dist_sp[v] > d2) {
                        dist_sp[v] = d2, depth_sp[v] = depth_sp[u] + 1, parent_sp[v] = u,
                        psi[v] = psi[u] + g;
                        que.emplace(d2, v);
                    }
                }
            }
        }

        uf_ps.assign(V, -1);
        using P = std::tuple<T, int, int>;
        std::priority_queue<P, std::vector<P>, std::greater<P>> que;
        for (int u = 0; u < V; u++) {
            if (dist_sp[u] == INF) continue;
            for (int i = 0; i < int(to[u].size()); i++) {
                int v;
                T l;
                G g;
                std::tie(v, l, g) = to[u][i];
                if (u < v and !(psi[u] + g == psi[v]))
                    que.emplace(dist_sp[u] + dist_sp[v] + l, u, i);
            }
        }

        dist.assign(V, INF);
        while (que.size()) {
            T h;
            int u0, i;
            std::tie(h, u0, i) = que.top();
            que.pop();
            const int v0 = std::get<0>(to[u0][i]);
            int u = _find(u0), v = _find(v0);
            std::vector<int> bs;
            while (u != v) {
                if (depth_sp[u] > depth_sp[v]) {
                    bs.push_back(u), u = _find(parent_sp[u]);
                } else {
                    bs.push_back(v), v = _find(parent_sp[v]);
                }
            }
            for (const int x : bs) {
                _unite(u, x);
                dist[x] = h - dist_sp[x];
                for (int i = 0; i < int(to[x].size()); i++) {
                    int y;
                    T l;
                    G g;
                    std::tie(y, l, g) = to[x][i];
                    if (psi[x] + g == psi[y]) { que.emplace(dist[x] + dist_sp[y] + l, x, i); }
                }
            }
        }
        for (int i = 0; i < V; i++) {
            if (!(psi[i] == G()) and dist_sp[i] < dist[i]) dist[i] = dist_sp[i];
        }
    }
};
/* Example of group G:
struct G {
    unsigned g;
    G(unsigned x = 0) : g(x) {}
    G operator-() const noexcept { return *this; }
    G operator+(const G &r) const noexcept { return G(g ^ r.g); }
    bool operator==(const G &x) const noexcept { return g == x.g; }
};
*/

struct XorG {
    unsigned g;
    XorG(unsigned x = 0) : g(x) {}
    XorG operator-() const noexcept { return *this; }
    XorG operator+(const XorG &r) const noexcept { return XorG(g ^ r.g); }
    bool operator==(const XorG &x) const noexcept { return g == x.g; }
};

#include <stdio.h>
#include <assert.h>
#include <math.h>
#include <algorithm>
#include <vector>
#include <array>
#include <map>
#include <queue>
#include <iostream>
#include <string>
#include <functional>

using namespace std;
typedef long long ll;
const int maxn = 200050;
const ll inf = 1ll<<60;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int n, m, K;
    cin >> n >> m >> K;
    ShortestNonzeroPath<ll, inf, XorG> g(n);
    for (int i=0; i<m; i++) {
        int a, b, c;
        string x;
        cin >> a >> b >> c >> x;
        int v = 0;
        for (int i=0; i<K; i++) {
            if (x[i] == '1') v |= (1 << i);
        }
        g.add_bi_edge(--a, --b, c, v);
    }
    g.solve(n-1);
    for (int i=0; i<n-1; i++) {
        ll ans = g.dist[i];
        if (ans >= inf) ans = -1;
        cout << ans << '\n';
    }
}

yukicoder

結果

テストケース

ソースコード