結果

問題 No.1602 With Animals into Institute 2
ユーザー nouka28
提出日時 2025-06-29 23:52:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 3,235 bytes
コンパイル時間 6,267 ms
コンパイル使用メモリ 335,044 KB
実行使用メモリ 37,656 KB
最終ジャッジ日時 2025-06-29 23:53:08
合計ジャッジ時間 22,853 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 3
other AC * 6 WA * 20 TLE * 1 -- * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

/*
https://arxiv.org/abs/1906.04062 の p17 の algorithm の実装をしています。
*/

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

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

	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);
		for(int v=0;v<n;v++){
			if(label_T[v]!=e()){
				q[v]=dist_T[v];
			}
		}

		dsu ds(n);
		vector<int> root(n);
		for(int v=0;v<n;v++){
			root[v]=v;
		}

		// 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]){
				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]){
					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[ds.leader(u[e])];
			int w2=root[ds.leader(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=root[pred_T[w1]];
			}

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

				for(auto&&f:g[w]){
					if(op(label_T[w],f.x)!=label_T[f.to])continue;
					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 : 結果を返す
		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