結果
問題 |
No.1602 With Animals into Institute 2
|
ユーザー |
|
提出日時 | 2025-06-30 00:51:48 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 382 ms / 4,000 ms |
コード長 | 3,746 bytes |
コンパイル時間 | 4,217 ms |
コンパイル使用メモリ | 296,412 KB |
実行使用メモリ | 40,060 KB |
最終ジャッジ日時 | 2025-06-30 00:52:01 |
合計ジャッジ時間 | 10,160 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 36 |
ソースコード
/* - https://arxiv.org/abs/1906.04062 の p17 の algorithm - https://gist.github.com/wata-orz/d3037bd0b919c76dd9ddc0379e1e3192 の実装をしています。 */ #include <bits/stdc++.h> using namespace std; using ll = long long; const ll inf = 1e18; using T = ll; ll op(ll a, ll b) { return a ^ b; } ll e() { return 0; } ll inv(ll x) { return x; } // template<class T,T(*op)(T,T),T(*e)(),T(*inv)(T)> struct shortest_non_zero_path { template <class U> using pqmin = priority_queue<U, vector<U>, greater<U>>; struct edge { int to; ll cost; T x; int id; bool is_consistent; }; int n, m; vector<vector<edge>> g; shortest_non_zero_path() {} shortest_non_zero_path(int n) : n(n), m(0), g(n) {} void add_edge(int u, int v, ll c, T x) { g[u].push_back({v, c, x, m}); g[v].push_back({u, c, inv(x), m}); m++; } vector<ll> solve(int s) { // step0: 最短路木の作成 vector<ll> dist_T(n, inf); vector<int> depth_T(n, -1); vector<int> pred_T(n, -1); vector<T> label_T(n, e()); pqmin<pair<ll, int>> pq_T; dist_T[s] = 0, depth_T[s] = 0, label_T[s] = e(); pq_T.push({dist_T[s], s}); while (pq_T.size()) { auto [d, p] = pq_T.top(); pq_T.pop(); if (dist_T[p] < d) continue; for (auto&& e : g[p]) { if (dist_T[e.to] > dist_T[p] + e.cost) { dist_T[e.to] = dist_T[p] + e.cost; depth_T[e.to] = depth_T[p] + 1; pred_T[e.to] = p; label_T[e.to] = op(label_T[p], e.x); pq_T.push({dist_T[e.to], e.to}); } } } // step1: q(v), uf の初期化 vector<ll> q(n, inf); vector<int> par(n, -1); auto root = [&](auto root, int x) -> int { if (par[x] == -1) return x; return par[x] = root(root, par[x]); }; auto merge = [&](int p, int c) -> void { par[c] = p; }; // step2: 非整合な e を列挙 vector<ll> h(m, inf); vector<int> u(m), v(m); pqmin<pair<ll, int>> pq_F; for (int i = 0; i < n; i++) { for (auto&& e : g[i]) { e.is_consistent = (op(label_T[i], e.x) == label_T[e.to]); u[e.id] = i, v[e.id] = e.to; if (!e.is_consistent) { h[e.id] = dist_T[i] + dist_T[e.to] + e.cost; pq_F.push({h[e.id], e.id}); } } } // step3: h が空になるまで実行する while (pq_F.size()) { // step3.1: pq_F から最小の h(e) なる e を取り、w1,w2 を計算 auto [he, e] = pq_F.top(); pq_F.pop(); if (h[e] != he) continue; int w1 = root(root, u[e]); int w2 = root(root, v[e]); // step3.2: B に wi を加え、unionfind の更新 set<int> B; while (w1 != w2) { if (depth_T[w1] < depth_T[w2]) swap(w1, w2); B.insert(w1); w1 = root(root, pred_T[w1]); } // step3.3: w\in B について処理 for (auto&& w : B) { merge(w1, w); q[w] = he - dist_T[w]; for (auto&& f : g[w]) { if (f.is_consistent) { if (h[f.id] > q[w] + dist_T[f.to] + f.cost) { h[f.id] = q[w] + dist_T[f.to] + f.cost; pq_F.push({h[f.id], f.id}); } } } } } // step4 : 最短路木で満たしている場合の更新 for (int i = 0; i < n; i++) { if (label_T[i] != e()) { q[i] = min(q[i], dist_T[i]); } } // step5 : 結果を返す return q; } }; int main() { cin.tie(nullptr)->sync_with_stdio(false); int N, M, K; cin >> N >> M >> K; vector<int> A(M), B(M), C(M), X(M); for (int i = 0; i < M; i++) { cin >> A[i] >> B[i] >> C[i]; A[i]--, B[i]--; string s; cin >> s; for (auto&& e : s) X[i] = 2 * X[i] + (e - '0'); } shortest_non_zero_path solver(N); for (int i = 0; i < M; i++) { solver.add_edge(A[i], B[i], C[i], X[i]); } auto d = solver.solve(N - 1); for (int i = 0; i < N - 1; i++) { if (d[i] == inf) cout << -1 << "\n"; else cout << d[i] << "\n"; } }