本文主要是介绍UVA_1599 Ideal Path，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意

给一个n个点m条边（2≤n≤100000，1≤m≤200000）的无向图，每条边上都涂有一种颜色。求从结点1到结点n的一条路径，使得经过的边数尽量少，在此前提下，经过边的颜色序列的字典序最小。一对结点间可能有多条边，一条边可能连接两个相同结点。输入保证结点1可以达到结点n。颜色为1～109的整数。

探索

理解题目

1. 所求是什么？
   所求是两点之间最短路径中的一个
2. 提供的数据是什么？
   n个结点和m条边

寻找关系，拟定方案

1. 这道题我们应该用什么数据结构来完成？
   图
2. 关于这道题，你有什么相关的图的基本模型你觉得可以使用？
   BFS，因为要求最短路径，是BFS，DFS对最短路径没有任何帮助
3. BFS有什么作用，在这个题目中可以利用
   BFS可以算出从一个结点出发到其他结点的最短距离
4. 为了充分应用这个算法，很明显，通过BFS算法我们可以得到长度的大小，但是还是没有办法得到路径，你有遇见过任何长度到具体对象的算法吗？
   。。。好像没有
5. 那如果我们没有现成的想法的时候，我们或许得先判断，是否我们能得到的条件满足目标？
   嗯，距离和选择的结点的关系应该是相互制约的，结点定了距离也就定了，而距离定了，我们得到的也就是能满足最短路径的所有路径了
6. 既然我们知道了是可以满足等价推导的条件的，你认为这个条件是什么？我是说为什么距离就决定了路径，用将路径单纯用距离表示
   我不知道。。但是肯定是距离会影响结点，结点也会影响长度
7. 很多时候当我们知道明摆着会有影响，但是我们去没有办法表示的时候，或许就是因为递归的思想，就像我们一开始写代码的时候，一时之间总觉得recursions难以理解，在现实生活中也会有这样的时候，现在我想你的感受或许和做recursion是一开始的感觉是一样的，就像我们对待recursion的策略一样，把规模降低降低，让我们从n变到足够低，画图永远是最直观的东西！话一个一目了然的情况，然后从画中标出我们想要得到，和我们已知的，在这里是我们的已知是每个结点的最短距离，我们想要的是路径
   
   感觉不太对，我不选4是因为1-5就是2而1-4=2说明肯定不经过4可以排除，但是要是说我选2和3因为是和1的距离是1<2也觉得还不对，要是2和3根本不到5呢？
8. 嗯，可见选这个结点条件是要能够到5并且其距离要每一次都是到5的距离减一，那么问题就变成了连通性的问题，我们可以使用dfs每个结点判断是否能到5，在进行判断，我想我们是会做的，但是是否，有点太过于复杂
   嗯，是的，每个结点都要判断，就。。。
9. 很多时候，一个事物从不同的角度看有不同的视角，或许从开头复杂，从结尾就简单了，多探索，多思考
   哦我明白了，从5出发，我反正所有的有距离的都是可以到5的，这样我们就可以知道，对每一个结点，它能走的下一个结点有那些，进行组合就可以得到所有的路线(这个要得到所有的路径是可以的，但是有很多的for循环！而且还不知道怎么记录)
   
10. 当然下一个条件是让我们找出the colors of passages inthe order they must be passed in the ideal path.首先回顾一下第3章中介绍的“字典序”。对于字符串来说，字典序就是在字典里的顺序。例如，ab在cd的前面，cde在a的后面，abcd在abcde的前面。这个定义可以扩展到序列：序列(1, 2)在(3, 4, 5)的前面，(4, 5, 6)在(4, 5)的后面。所有我们要找到在所有段中可走的线路中最短的一个！---其实这个让这个题目变简单了。。。

tip:
一对结点间可能有多条边，一条边可能连接两个相同结点
一开始处理，不要环，选取两个结点之间最近的点

经验

解题方法：

1. 数据结构确定
2. 选择算法
3. 当我们选择了相似的算法之后，却依旧觉得很遥远的时候，我们要使用等价判断，看看我们已知的数据是否是等价的，是否可以推出来
4. 当我们明析了数据是可以实现等价的时候，去常常觉得难以描述，我们要思考是否是因为recursion，而对付recursion最好的方法就是规模减少+画图
5. 注意：画图永远要有最简单的图示表达 当我们想要使用画图使用未知表达已知，我们就要在图中画出已知，然后画出我们要得到的，然后去观察思考
6. 当我们解题的时候，已经有了差不多的解法，却觉得不过大气简洁的时候，或许我们需要换一个视角，就像看的《今日说法-烟锁殡仪馆》从受害者入手感到困难，我们就推导杀害人，或许会看见不一样的东西，从头或从尾
   图：
7. 图_双向bfs 双向bfs+字典序
8. 图_存储_邻接矩阵 图的边的存储，太大，不能用数组
   代码：
9. 循环_明析自己到底要什么不要无脑的就是index 想要的是结点，但是之间顺手地就写i，j...

// 错误
for (int i = 0; i < next.size(); i++) {
			for (int j = 0; j < edge[i].size(); j++) {
// 正确
for (int i = 0; i < next.size(); i++) {
			int thisedge = next[i];
			for (int j = 0; j < edge[thisedge].size(); j++) {

代码

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>
//#define LOCAL
using namespace std;
const int maxn = 100000+5;
const int INF = 1e9;
struct Edge
{
	int u;
	int v;
	int c;
	Edge(int a,int b,int d):u(a),v(b),c(d){}
};
vector<Edge> edge[maxn];
int d[maxn];
int used[maxn];
int n, m;

void rebfs() {
	memset(d, -1, sizeof(d));
	memset(used, 0, sizeof(used));
	queue<int> que;
	que.push(n);
	used[n] = 1; d[n] = 0;
	while (que.size()) {
		int nownode = que.front(); que.pop();
		for (int i = 0; i < edge[nownode].size(); i++) {
			int nexnode = edge[nownode][i].v;
			if (!used[nexnode]) {
				d[nexnode] = d[nownode] + 1;
				used[nexnode] = 1;
				que.push(nexnode);
			}
		}
	}
}

vector<int> answer;
void bfs() {
	memset(used, 0, sizeof(used));
	answer.clear();

	vector<int> next;
	used[1] = 1;
	next.push_back(1);
	int path = d[1];
	while (path--) {
		int min = INF;
		for (int i = 0; i < next.size(); i++) {
			int thisedge = next[i];
			for (int j = 0; j < edge[thisedge].size(); j++) {
				int theedge = edge[thisedge][j].v;
				if (d[theedge] == d[thisedge] - 1 && edge[thisedge][j].c < min)
					min = edge[thisedge][j].c;
			}
		}
		answer.push_back(min);
		vector<int> next2;
		for (int i = 0; i < next.size(); i++) {
			int thisedge = next[i];
			for (int j = 0; j < edge[thisedge].size(); j++) {
				int theedge = edge[thisedge][j].v;
				if (d[theedge] == d[thisedge] - 1 && edge[thisedge][j].c == min && !used[theedge]) {
					next2.push_back(theedge);
					used[theedge] = 1;
				}	
			}
		}
		next = next2;
	}
}

int main() {
#ifdef LOCAL
	freopen("output.txt", "w", stdout);
#endif // LOCAL

	while (scanf("%d%d", &n, &m) == 2) {
		for (int i = 0; i <= n; i++) {
			edge[i].clear();
		}
		int a = m;
		while (a--)
		{
			int u, v, c;
			cin >> u >> v >> c;
			if (u != v) {
				Edge e = Edge(u, v, c);
				edge[u].push_back(e);
				e = Edge(v, u, c);
				edge[v].push_back(e);
			}
		}

		rebfs();
		bfs();
		printf("%d\n", d[1]);
		for (int i = 0; i < answer.size(); i++) {
			if (i == 0) printf("%d", answer[i]);
			else printf(" %d", answer[i]);
		}
		printf("\n");

		
	}
	
	return 0;
}

这篇关于UVA_1599 Ideal Path的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！