提出 #66779449

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll=long long;
int n,m;
vector<vector<pair<int,int>>> graph;
vector<tuple<int,int,int>> edges;
vector<int> d;
vector<bool> visited;
vector<int> basis;
queue<int> q;
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	graph.resize(n+1);
	edges.resize(m);
	d.assign(n+1,-1);
	visited.assign(n+1,false);
	for(int i=0;i<m;i++){
		int u,v,w;cin>>u>>v>>w;
		graph[u].push_back({v,w});
		edges[i]=make_tuple(u,v,w);
	}
	d[1]=0;
	visited[1]=true;
	q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(auto&p:graph[u]){
			int v=p.first,w=p.second;
			if(!visited[v]){
				visited[v]=true;
				d[v]=d[u]^w;
				q.push(v);
			}
		}
	}
	if(!visited[n]){
		cout<<-1<<endl;
		return 0;
	}
	for(auto&e:edges){
		int u,v,w;tie(u,v,w)=e;
		if(visited[u]&&visited[v]){
			int x=d[u]^w^d[v];
			for(int b:basis)x=min(x,x^b);
			if(x!=0)basis.push_back(x);
		}
	}
	sort(basis.begin(),basis.end(),greater<int>());
	ll ans=d[n];
	for(int b:basis)ans=min(ans,ans^b);
	cout<<ans<<endl;
	return 0;
}

提出情報

ジャッジ結果