UVA

传送门

题意

求带边权无向图从起点到终点的边权字典序最小的最短路路径

解法

两遍 BFS
第一遍逆向，给图分层
第二遍求路径，每层的点都只能沿最小的边权走向下一层的点。

代码

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <queue>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int MAXN=1e5+10;

int n,m;
int head[MAXN],nxt[MAXN*4],to[MAXN*4],c[MAXN*4],tot=1;
int dis[MAXN],from[MAXN],path[MAXN];
bool vis[MAXN];
queue<int> que;
queue<vector<int> > q2;

void add(int u,int v,int w){
	to[++tot]=v;c[tot]=w;nxt[tot]=head[u];head[u]=tot;
	to[++tot]=u;c[tot]=w;nxt[tot]=head[v];head[v]=tot;
}

void bfs1(){
	while(!que.empty()) que.pop();
	memset(dis,0x3f,sizeof(dis));
	dis[n]=0;que.push(n);
	while(!que.empty()){
		int u=que.front();que.pop();
		for(int i=head[u];i;i=nxt[i])
			if(dis[to[i]]>dis[u]+1){
				dis[to[i]]=dis[u]+1;
				que.push(to[i]);
			}
	}
}
void bfs2(){
	memset(path,0x3f,sizeof(path));
	memset(vis,0,sizeof(vis));
	vector<int> vec;
	vec.push_back(1);
	q2.push(vec);
	while(!q2.empty()){
		vector<int> uv=q2.front();q2.pop();
		vec.clear();
		int color=inf;
		for(int i=0;i<uv.size();i++){
			int u=uv[i];
			for(int j=head[u];j;j=nxt[j])
				if(dis[to[j]]==dis[u]-1)
					color=min(color,c[j]);
		}
		for(int i=0;i<uv.size();i++){
			int u=uv[i];
			for(int j=head[u];j;j=nxt[j])
				if(dis[to[j]]==dis[u]-1&&c[j]==color&&!vis[to[j]]){
					from[to[j]]=u;
					path[to[j]]=color;
					vec.push_back(to[j]);
					vis[to[j]]=1;
				}
		}
		if(!vec.empty()) q2.push(vec);
	}
}

void print(int now){
	if(now==1) return;
	print(from[now]);
	printf("%d",path[now]);
	if(now!=n) printf(" ");
}

void solve(){
	tot=1;
	memset(head,0,sizeof(head));
	for(int i=1,u,v,w;i<=m;i++){
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
	}
	bfs1();
	bfs2();
	printf("%d
",dis[1]);
	print(n);
	printf("
");
}

int main(){
	while(~scanf("%d%d",&n,&m))
		solve();
	return 0;
}