結果

問題 No.1602 With Animals into Institute 2
ユーザー nouka28
提出日時 2025-06-30 01:19:52
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 401 ms / 4,000 ms
コード長 4,203 bytes
コンパイル時間 3,373 ms
コンパイル使用メモリ 294,408 KB
実行使用メモリ 40,412 KB
最終ジャッジ日時 2025-06-30 01:20:05
合計ジャッジ時間 10,665 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

using ll = long long;
const ll inf = 1e18;

namespace cplib {

	template <class Monoid>
	struct shortest_non_zero_path {
		template <class U>
		using pqmin = priority_queue<U, vector<U>, greater<U>>;

		struct edge {
			int to;
			ll cost;
			typename Monoid::value_type 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) {}

		inline void add_edge(int u, int v, ll c, typename Monoid::value_type x) {
			g[u].push_back({v, c, x, m});
			g[v].push_back({u, c, Monoid::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<typename Monoid::value_type> label_T(n, Monoid::e());
			pqmin<pair<ll, int>> pq_T;
			dist_T[s] = 0, depth_T[s] = 0, label_T[s] = Monoid::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] = Monoid::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 = (Monoid::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 の更新

				vector<int> B;

				while (w1 != w2) {
					if (depth_T[w1] < depth_T[w2]) swap(w1, w2);
					B.push_back(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] != Monoid::e()) {
					q[i] = min(q[i], dist_T[i]);
				}
			}

			// step5 : 結果を返す

			return q;
		}
	};

	/*
	Shortest Non Zero Path

	ref :
	- https://arxiv.org/abs/1906.04062
	- https://gist.github.com/wata-orz/d3037bd0b919c76dd9ddc0379e1e3192
	*/
}  // namespace cplib

struct Monoid_Xor {
	using value_type = ll;
	ll x;
	static ll op(ll x, ll y) {
		return x ^ y;
	}
	static ll inv(ll x) {
		return x;
	}
	static ll e() {
		return 0;
	}
	static constexpr bool commute = true;
};

ll op(ll a, ll b) {
	return a ^ b;
}
ll id() {
	return 0;
}
ll inv(ll x) {
	return x;
}

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');
	}

	cplib::shortest_non_zero_path<Monoid_Xor> 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";
	}
}
0