UVA1599理想路径题解

题目

链接

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

字面描述

给定一个n个点m条边的无向图，每条边上都涂有1种颜色。求点1到点n的一条路径，使得经过的边数最少，在此前提下，经过边的颜色序列最小。可能有自环与重边。输入保证至少存在一条连接1和n的道路。
2≤n≤10 ^5
1≤m≤2×10^5
1≤ci≤10^9

题目思路

1. 从n反向遍历到1BFS，得出最短路和每层层数
2. 从1向层-1的子节点父节点，进行比较记录最小值

代码实现

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