結果

問題 No.1602 With Animals into Institute 2
コンテスト
ユーザー hitonanode
提出日時 2021-07-10 16:43:50
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 956 ms / 4,000 ms
コード長 4,714 bytes
コンパイル時間 1,668 ms
コンパイル使用メモリ 107,200 KB
最終ジャッジ日時 2025-01-23 00:24:44
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// Single-source unorthodox shortest paths
// Complexity: O(M log M)
// This implementation is based on: https://gist.github.com/wata-orz/d3037bd0b919c76dd9ddc0379e1e3192
template <class T, T INF, class G, G (*op)(G, G), G (*e)()> struct SSSUP {
    int V;
    std::vector<std::vector<std::tuple<int, T, G>>> to;
    SSSUP(int n) : V(n), to(n) { static_assert(INF > 0, "INF must be positive"); }
    void add_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.inv());
    }

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;
    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, e());
            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 = e();
                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] = op(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++) {
            for (int i = 0; i < int(to[u].size()); i++) {
                int v;
                T l;
                G g = e();
                std::tie(v, l, g) = to[u][i];
                if (u < v and !(op(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 = e();
                    std::tie(y, l, g) = to[x][i];
                    if (op(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] == e()) and dist_sp[i] < dist[i]) dist[i] = dist_sp[i];
        }
    }
};

struct G {
    unsigned g;
    G(unsigned x) : g(x) {}
    G inv() const { return *this; }
    bool operator==(const G &x) const { return g == x.g; }
};
G op(G x, G y) { return G(x.g ^ y.g); }
G e() { return G(0); }

#include <iostream>
using namespace std;
int main() {
    int N, M, K;
    cin >> N >> M >> K;
    constexpr long long INF = 1LL << 60;
    SSSUP<long long, INF, G, op, e> graph(N);

    vector<tuple<int, int, int>> edges;
    while (M--) {
        int a, b, c;
        string x;
        cin >> a >> b >> c >> x;
        unsigned m = 0;
        for (auto c : x) m = m * 2 + c - '0';
        a--, b--;
        graph.add_edge(a, b, c, m);
        graph.add_edge(b, a, c, m);
    }
    graph.solve(N - 1);
    for (int i = 0; i < N - 1; i++) {
        cout << (graph.dist[i] == INF ? -1 : graph.dist[i]) << '\n';
    }
}
0