Submission #2860677

---

Source Code Expand

#include<bits/stdc++.h>
#define inf 1e8
using namespace std;
struct edge{
	int c,u,v;
	edge(int a,int b,int d):u(a),v(b),c(d) {}
};
vector<edge> e;
set<int> adj[300005];
vector<int> g[300005];
int par[300005],dis[300005],n,m;
void init(){
	for(int i=0;i<=300005;i++){
		par[i]=i; 
		dis[i]=1e8;
	}
}
int find(int i){
	if(par[i]==i) return par[i];
	return par[i]=find(par[i]);
}
void dsu(int i,int j){
	par[find(i)]=find(j);
}
void bfs(){
	dis[1]=0;
	queue<int> q; q.push(1);
	while(!q.empty()){
		int u=q.front();q.pop();
		for(set<int>::iterator it=adj[u].begin();it!=adj[u].end();it++){
			if(dis[*it]>dis[u]+1){
				dis[*it]=min(dis[*it],dis[u]+1);
				q.push(*it);
			}
		}
	}
	if(dis[n]==inf){
	 	cout<<"-1";  
		exit(0);
	}
	else cout<<dis[n]/2; exit(0);
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	for(int  i=1; i<=m; i++){
		int c,u,v;
		cin>>u>>v>>c;
		g[u].push_back(e.size());
		g[v].push_back(e.size());
		e.push_back(edge(u,v,c));
	}
	init();
	for(int i=0;i<e.size();i++){
		int u=e[i].u;
		for(int j: g[u]){
			if(e[j].c==e[i].c&&i!=j){
				dsu(i,j);
			}
		}
		int v=e[i].v;
		for(int j: g[v]){
			if(e[j].c == e[i].c&&i!=j){
				dsu(i,j);
			}
		}
	}
	for(int i=0;i<e.size();i++){
		adj[par[i]+n+1].insert(e[i].u);
		adj[par[i]+n+1].insert(e[i].v);
		adj[e[i].v].insert(par[i]+1+n);
		adj[e[i].u].insert(par[i]+1+n);
	}
	bfs();
}

Submission Info

Compile Error

./Main.cpp: In function ‘void init()’:
./Main.cpp:14:11: warning: iteration 300005u invokes undefined behavior [-Waggressive-loop-optimizations]
   par[i]=i; 
           ^
./Main.cpp:13:15: note: containing loop
  for(int i=0;i<=300005;i++){
               ^

Judge Result