Uva1599 ideal path problem solution

subject

link

https://www.luogu.com.cn/problem/UVA1599

Literal description

Given a n A little bit m Undirected graph of strip and edge , Each side is painted 1 Color . Find the point 1 point-to-point n A path for , To minimize the number of sides to pass , Under this premise , The color sequence passing through the edge is the smallest . There may be self rings and double edges . Input ensures that at least one connection exists 1 and n The path of .
2≤n≤10 ^5
1≤m≤2×10^5
1≤ci≤10^9

Topic ideas

1. from n Traverse backward to 1BFS, Get the shortest circuit and the number of layers of each layer
2. from 1 Directional layer -1 The child node of the parent node , Compare and record the minimum

Code implementation

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

const int maxn=4e5+10;
const int inf=1e9;
int n,m;
int dis[maxn],vis[maxn],que[maxn],ans[maxn];
vector< pair<int,int> >e[maxn];
int main(){
    
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
    
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		if(a==b)continue;
		e[a].push_back(make_pair(b,c));
		e[b].push_back(make_pair(a,c));
	}
	for(int i=0;i<=n;i++)ans[i]=inf;
	int head=0,tail=0;
	que[tail++]=n;
	vis[n]=true;
	while(head<tail){
    
		int x=que[head++];
		if(x==1)break;
		for(int i=0;i<e[x].size();i++){
    
			if(!vis[e[x][i].first]){
    
				vis[e[x][i].first]=true;
				que[tail++]=e[x][i].first;
				dis[e[x][i].first]=dis[x]+1;
			}
		}
	}
	//for(int i=1;i<=n;i++)printf("%d ",dis[i]);
	//printf("\n");
	printf("%d\n",dis[1]);
	memset(vis,false,sizeof(vis));
	vis[1]=true;
	head=0,tail=0;
	que[tail++]=1;
	while(head<tail){
    
		int x=que[head++];
		for(int i=0;i<e[x].size();i++){
    
			if(dis[e[x][i].first]==dis[x]-1){
    
				vis[e[x][i].first]=true;
				que[tail++]=e[x][i].first;
				ans[dis[1]-dis[e[x][i].first]]=min(ans[dis[1]-dis[e[x][i].first]],e[x][i].second);
			}
		}
	}
	for(int i=1;i<=dis[1];i++)printf("%d ",ans[i]);
	return 0;
}