Submission #2861310

---

Source Code Expand

#include<bits/stdc++.h>
#define inf 1e18
#define int long long
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;
bool vis[200005];
set<int> adj[300005];
vector<int> g[100005];
int dis[300005],n,m,cnt;
vector<int> Set[300005];
void dfs_edge(int e,int color){
	vis[e]=1;
	Set[cnt].push_back(e);
	for(int j:g[E[e].u]){
		if(!vis[j]&&E[j].c==color){
			dfs_edge(j,color);
		}
	}
	for(int j:g[E[e].v]){
		if(!vis[j]&&E[j].c==color){
			dfs_edge(j,color);
		}
	}
}
void dick(){
	dis[1]=0;
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > q; q.push(make_pair(0,1));
	while(!q.empty()){
		int u=q.top().second; int dist=q.top().first; q.pop();
		if(dis[u]<dist) continue;
		for(set<int>::iterator it=adj[u].begin();it!=adj[u].end();it++){
			if(dis[*it]>dis[u]+1){
				dis[*it]=dis[u]+1;
				q.push(make_pair(dis[*it],*it));
			}
		}
	}
	if(dis[n]==inf){
	 	cout<<"-1";  
		exit(0);
	}
	else cout<<dis[n]/2; exit(0);
}
signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin>>n>>m;
	cnt=0;
	for(int i=0;i<=300000;i++){
		dis[i]=1e8;
	}
	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));
	}
	for(int i=0;i<E.size();i++){
		if(!vis[i]){
			dfs_edge(i,E[i].c);
			cnt++;
		}
	}
	cnt--;
	for(int i=0;i<cnt;i++){
		for(int j=0;j<Set[i].size();j++){
			int e=Set[i][j];
			adj[i+n+1].insert(E[e].u);
			adj[i+n+1].insert(E[e].v);
			adj[E[e].u].insert(i+n+1);
			adj[E[e].v].insert(i+n+1);
		}
	}
	dick();
}

Submission Info

Judge Result