結果

問題 No.1602 With Animals into Institute 2
ユーザー nouka28
提出日時 2025-06-30 00:59:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 371 ms / 4,000 ms
コード長 3,456 bytes
コンパイル時間 4,001 ms
コンパイル使用メモリ 294,320 KB
実行使用メモリ 40,684 KB
最終ジャッジ日時 2025-06-30 00:59:56
合計ジャッジ時間 10,358 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
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;
}

// 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){}

	inline 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 の更新

			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]!=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";
	}
}
0