UVA-1599 理想路径 题解答案代码 算法竞赛入门经典第二版

GitHub - jzplp/aoapc-UVA-Answer: 算法竞赛入门经典 例题和习题答案 刘汝佳 第二版

本题目是在普通最短路的基础上，加上了路径标识（颜色），根据路径标识做进一步筛选。

我使用了两次BFS完成这道题目：

第一次是遍历整个图，标注出每个节点到终点的距离。实际上是为了给第二次遍历缩小范围。

这一次遍历实际上就已经得到了不包含路径标识（颜色信息）的最短路径。

第二次是根据上一次遍历得到的最短路径结果，根据颜色信息筛选出符合要求的最短路。

这个题目还有几点需要注意：

题目结点数据量太大，直接用邻接矩阵无法存储，可以使用邻接表。

遍历的时候注意减少不必要的遍历情况，比如那些确定不是最短路的路径结点不能再加入队列，队列中也不要有重复的结点。

由于邻接表查找某条路径耗时较多，因此第二次遍历时可以存储下当前最短路径的颜色信息。

AC代码

#include
#include
#include
#include
#include
 
#define MAXN 100002
using namespace std;
 
struct Edge {
	int b, c;
};
 
vector ve[MAXN];
int flagEnd[MAXN];
int flagFront[MAXN];
int pathFront[MAXN];
int path[MAXN];
int n;
 
void clear() {
	memset(flagEnd, 0, sizeof(flagEnd));
	memset(flagFront, 0, sizeof(flagFront));
	memset(pathFront, 0, sizeof(pathFront));
	memset(path, 0, sizeof(path));
	fill(ve, ve + MAXN, vector());
} 
 
void bfsEnd() {
	int i, j;
	queue<int> qu;
	qu.push(n);
	flagEnd[n] = 1;
	while(!qu.empty()) {
		i = qu.front();
		qu.pop();
		for(j = 0; j < ve[i].size(); ++j) {
			if(!flagEnd[ve[i][j].b]) {
				flagEnd[ve[i][j].b] = flagEnd[i] + 1;
				qu.push(ve[i][j].b);
			}
		}
	}
}
 
void bfsBeg() {
	int i, j, k, f;
	flagFront[1] = 0;
	pathFront[1] = 0;
	queue<int> qu;
	qu.push(1);
	while(!qu.empty()) {
		i = qu.front();
		qu.pop(); 
		f = 1000000001;
		for(j = 0; j < ve[i].size(); ++j) {
			k = ve[i][j].b;
			if(flagEnd[k] != flagEnd[i] - 1) continue;
			if(ve[i][j].c >= f) continue;
			f = ve[i][j].c;
			if(flagFront[k] && pathFront[k] < f) {
				f = pathFront[k];
			}
		} 
		for(j = 0; j < ve[i].size(); ++j) {
			k = ve[i][j].b;
			if(ve[i][j].c != f || flagEnd[k] != flagEnd[i] - 1) continue;
			if(flagFront[k] && pathFront[k] > f || !flagFront[k]) {
				qu.push(k);
				flagFront[k] = i;
				pathFront[k] = f;
			}
		}
	}
}
 
int getPath() {
	int i = n, j = 0;
	while(flagFront[i]) {
		path[j] = pathFront[i];
		i = flagFront[i];
		++j; 
	}
	return j;
} 
 
void input(int m) {
	int a, b, c;
	for(int i = 0; i < m; ++i) {
		scanf("%d %d %d", &a, &b, &c);
		if(a == b) continue;
		ve[a].push_back({b, c});
		ve[b].push_back({a, c});
	}
}
 
int main() {
	int m, i, j, k;
	int a, b, c;
	while(scanf("%d %d", &n, &m) == 2) {
		clear();
		input(m);
		bfsEnd();
		bfsBeg();
		j = getPath();
		printf("%d\n", j);
		for(i = j - 1; i >= 0; --i) {
			if(i != j - 1) {
				putchar(' ');
			}
			printf("%d", path[i]);
		}
		putchar('\n');
	}
	return 0;
}