Uva 1599 / POJ 3967 Ideal Path：不一样的 BFS

This blog post is only available in Simplified Chinse.

题目链接：UVa 1599 Ideal Path 或者 POJ 3967 Ideal Path

POJ 上居然不能用 vector ！！！强烈不满！

（本博客以 UVa 上的题目为准）

Problem

New labyrinth attraction is open in New Lostland amusement park. The labyrinth consists of n rooms connected by m passages. Each passage is colored into some color ci. Visitors of the labyrinth are dropped from the helicopter to the room number 1 and their goal is to get to the labyrinth exit located in the room number n.

Labyrinth owners are planning to run a contest tomorrow. Several runners will be dropped to the room number 1. They will run to the room number n writing down colors of passages as they run through them. The contestant with the shortest sequence of colors is the winner of the contest. If there are several contestants with the same sequence length, the one with the ideal path is the winner. The path is the ideal path if its color sequence is the lexicographically smallest among shortest paths.

Andrew is preparing for the contest. He took a helicopter tour above New Lostland and made a picture of the labyrinth. Your task is to help him find the ideal path from the room number 1 to the room number n that would allow him to win the contest.

Note: A sequence (a1, a2, . . . , ak) is lexicographically smaller than a sequence (b1, b2, . . . , bk) if there exists i such that ai < bi , and aj = bj for all j < i.

Input

The input file contains several test cases, each of them as described below. The first line of the input file contains integers n and m — the number of rooms and passages, respectively $(2 ≤ n ≤ 100000, 1 ≤ m ≤ 200000)$ . The following m lines describe passages, each passage is described with three integer numbers: ai, bi, and ci — the numbers of rooms it connects and its color $(1 ≤ a_i, b_i ≤ n, 1 ≤ c_i ≤ 10^9)$ . Each passage can be passed in either direction. Two rooms can be connected with more than one passage, there can be a passage from a room to itself. It is guaranteed that it is possible to reach the room number n from the room number 1.

Output

For each test case, the output must follow the description below. The first line of the output file must contain k — the length of the shortest path from the room number 1 to the room number n. The second line must contain k numbers — the colors of passages in the order they must be passed in the ideal path.

Sample Input

Sample Output

2
1 3

Analysis

这题是《算法竞赛入门经典》上面的原题，在书上作者还加粗标注：**“此题非常重要，强烈建议读者编写程序！”**但是写起来似乎并没有这么简单……

想法比较简单，如果光问我们最短路径，这就是入门题；关键是要让最短路径上颜色字典序最小，并且还要输出。可以从终点 n 开始反向 BFS，求出每个点到 n 点的距离 $dist(n)$ ，这样处理的好处是：在之后正向 BFS 处理的时候，可以方便地得出某个点是否在最短路径中。处理好反向的 BFS 之后，处理正向的求答案的 BFS 才是重头戏。其实也是 BFS 的思想，但是写起来却不像我们平常的“维护一个队列”的 BFS。我们需要把每步可能的走法都单独维护。具体处理起来还有技巧：将所有下一步的可能全都存在 vector 里，然后排序去重，加入下次的处理队列里。这样很大程度地避免了元素重复与空间浪费。具体实现的时候，可以用两个 vector，一个 now，一个 next。详见代码的 GetAns 部分～

emm，咨询 dalao 听说，据说 POJ 是不能用 vector 的……害怕…… ~~代码懒得改了……~~

Code

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn=100005,maxe=400005;
int T,n,e,dst[maxn],INF,dist=0;
bool vis[maxn];
struct VertexInfo{
	int x,c;
};
vector<int> ans,edge[maxn],color[maxn];
vector<VertexInfo> now,nxt;
queue<int> que;
inline int read(){
	int ret=0,f=1;char ch=getchar();
	while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
	while (ch>='0'&&ch<='9') ret=ret*10+ch-'0',ch=getchar();
	return ret*f;
}
inline void init(){
	memset(dst,0x3f,sizeof(dst));INF=dst[0];
	for (int i=1;i<=n;i++) edge[i].clear(),color[i].clear();
}
inline void BFS(int s){
	memset(vis,0,sizeof(vis));
	que.push(s);vis[s]=1;dst[s]=0;
	while (!que.empty()){
		int x=que.front();que.pop();
		for (int i=0;i<edge[x].size();i++) if (!vis[edge[x][i]]){
			vis[edge[x][i]]=true;
			dst[edge[x][i]]=dst[x]+1;
			que.push(edge[x][i]);
		}
	}
}
inline bool CompareColor(VertexInfo aa,VertexInfo bb){
	return aa.c<bb.c||(aa.c==bb.c&&aa.x<bb.x);
}
inline void GetAns(int s){
	memset(vis,0,sizeof(vis));ans.clear();
	//Init Vector "now"
	vis[s]=1;now.clear();
	now.push_back((VertexInfo){s,-1});

	for (int t=1;t<=dist;t++){ // Do BT BFS
		nxt.clear();
		for (int i=0;i<now.size();i++){
			VertexInfo head=now[i];
			for (int j=0;j<edge[head.x].size();j++) if (!vis[edge[head.x][j]]){
				if (t+dst[edge[head.x][j]]!=dist) continue;
				nxt.push_back((VertexInfo){edge[head.x][j],color[head.x][j]});
			}
		}

		now.clear();
		sort(nxt.begin(),nxt.end(),CompareColor);
		for (int i=0;i<nxt.size()&&nxt[i].c==nxt[0].c;i++){
			if (i!=0&&nxt[i].x==nxt[i-1].x) continue;
			now.push_back(nxt[i]);
			vis[nxt[i].x]=true;
		}
		ans.push_back(now[0].c);
	}
}
int main(){
	while (scanf("%d%d",&n,&e)!=-1){
		init();
		for (int i=1;i<=e;i++){
			int x=read(),y=read(),z=read();
			edge[x].push_back(y);color[x].push_back(z);
			edge[y].push_back(x);color[y].push_back(z);
		}
		BFS(n);dist=dst[1];
		GetAns(1);
		printf("%d\n",(int)ans.size());
		printf("%d",ans[0]);
		for (int i=1;i<ans.size();i++) printf(" %d",ans[i]);
		printf("\n");
	}
	return 0;
}

8/7/2018