結果

問題 No.1602 With Animals into Institute 2
ユーザー nouka28
提出日時 2025-06-30 00:39:21
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 515 ms / 4,000 ms
コード長 3,239 bytes
コンパイル時間 4,280 ms
コンパイル使用メモリ 296,124 KB
実行使用メモリ 35,572 KB
最終ジャッジ日時 2025-06-30 00:39:36
合計ジャッジ時間 14,135 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
- 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;
}

struct UnionFind{
	vector<int> ps;
	UnionFind(int n):ps(n,-1){}

	int find(int x){
		if(ps[x]==-1)return x;
		int r=find(ps[x]);
		ps[x]=r;
		return r;
	}

	void unite(int r,int c){
		ps[c]=r;
	}
};

// 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;
	};

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

		UnionFind uf(n);

		// step2: 非整合な e を列挙

		vector<int> u(m),v(m);
		pqmin<pair<ll,int>> pq_F;
		for(int i=0;i<n;i++){
			for(auto&&e:g[i]){
				if(i>e.to)continue;
				u[e.id]=i,v[e.id]=e.to;
				if(op(label_T[i],e.x)!=label_T[e.to]){
					pq_F.push({dist_T[i]+dist_T[e.to]+e.cost,e.id});
				}
			}
		}

		// step3: h が空になるまで実行する

		while(pq_F.size()){
			
			// step3.1: pq_F から最小の h(e) なる e を取り、w1,w2 を計算

			auto[h,e]=pq_F.top();pq_F.pop();

			int w1=uf.find(u[e]);
			int w2=uf.find(v[e]);

			// step3.2: B に wi を加え、dsu の更新

			set<int> B;
			while(w1!=w2){
				if(depth_T[w1]<depth_T[w2])swap(w1,w2);
				
				B.insert(w1);
				w1=uf.find(pred_T[w1]);
			}

			// step3.3: w\in B について処理
			for(auto&&w:B){
				uf.unite(w1,w);
				q[w]=h-dist_T[w];

				for(auto&&f:g[w]){
					if(op(label_T[w],f.x)==label_T[f.to]){
						pq_F.push({q[w]+dist_T[f.to]+f.cost,f.id});
					}
					
				}
			} 
		}

		for(int i=0;i<n;i++){
			if(label_T[i]!=e()){
				q[i]=min(q[i],dist_T[i]);
			}
		}

		// step4 : 結果を返す
		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";
	}
}
0