首页 > 代码库 > 初学算法之uva1599 IdealPath
初学算法之uva1599 IdealPath
题目:给一个n个点和m条边的无向图,每条边都涂有一种颜色。求从结点1到结点n的一条路径,使得经过的边数尽量少,在此前提下,经过边的颜色序列的字典序最小。一对结点间可能有多条边,一条边可能连接两个相同结点。输入保证结点1可以达到结点n。颜色1~1000000000(不用数了,九个零,忘记怎么弄上标了,也懒得去查)。
思路:这道题目需要采用正反两次bfs,先是反着用一次,求得每个结点到终点的路径,再具体一点就是求得结点1到所求结点的最短路径。然后再正着开始走,看是每次到达一个新结点时要保证d值恰好减一,直到到达终点。这里我分析一下为什么不能用一次bfs:我们假设用一次,首先从结点1出发,但是这个时候就不知道选择的最小权值的那个路径能不能到达。如图所示,如果选择结点5,则永远不能到达最终结点8.但是反向bfs后,就不能选择结点5了,因为,结点5比结点2到结点8的距离更远。这下就应该明白了。
talk is cheap ,show me your code!
1 #include<cstdio> 2 #include<vector> 3 #include<queue> 4 #include<cstring> 5 using namespace std; //min()函数 6 #define max 100000 7 #define inf 10000000+10 8 bool vis[max],in_q[max]; 9 int m,n,a,b,c;//边数、结点数、结点、下一个结点、颜色 10 int d[max];//记录各节点到终点的路径长度 11 int res[max];//记录最短路的权值 12 13 typedef struct edge { 14 int pot, color; 15 edge(int v = 0, int c = 0) :pot(v), color(c){} 16 }Edge;//还有这种操作,我也是第一次用,赋值很方便 17 18 vector<Edge>map[max];//记录邻接表 19 void re_bfs() { 20 int u, v; 21 memset(vis,0,sizeof(vis)); 22 memset(in_q, 0, sizeof(in_q)); 23 queue<int>q; 24 q.push(n - 1); 25 vis[n - 1] = true; 26 d[n - 1] = 0; 27 //在map里面存在着所有的节点以及他们之间的连接关系。map【u】.size代表着节点u相连节点的个数; 28 while (!q.empty()) { 29 u = q.front(); q.pop(); vis[u] = true; 30 for (int i = 0; i < map[u].size(); i++) { 31 v = map[u][i].pot; 32 if (!vis[v]&&!in_q[v]) { 33 vis[v] = true; 34 d[v] = d[u] + 1; 35 q.push(v); 36 in_q[v] = true; 37 } 38 } 39 } 40 } 41 42 void bfs() { 43 memset(in_q, 0, n); 44 memset(vis, 0, sizeof(vis)); 45 int u, v; 46 queue<int>q; 47 q.push(0); 48 memset(res, 0, n*sizeof(int));//res这个数组,存储了每个最短路径里面每条边的权值 49 while (!q.empty()) { 50 u = q.front(); q.pop(); vis[u] = true; 51 int minc = inf, num = map[u].size(); 52 for (int i = 0; i < num; i++) {//这个循环是找出与节点u相连的边的最小权值 53 v = map[u][i].pot; 54 if (!vis[v] && d[u] - 1 == d[v]) 55 minc = min(map[u][i].color, minc); 56 } 57 for (int i = 0; i < num; i++) {//最小权值的边不一定是一个,所以把所对应的另一个结点压入队列 58 v = map[u][i].pot; 59 if (!vis[v] && d[u] - 1 == d[v] && map[u][i].color == minc && !in_q[v]) 60 q.push(v); in_q[v] = true; 61 } 62 int index = d[0] - d[u];//这里就有学问了,因为就不仅要求得最短的路径,还要满足这些边是相连的 63 if (res[index] == 0)res[index] = minc; 64 else { 65 if (minc > res[index]) {//这里把前一段权值相同的,而压入队列的几个结点pop出去较大的,留下最下的,如果实在不懂,就把(121)(131)(243)(352)(464)(565)画一个图就明白了。 66 int temp_minc = q.front(); q.pop(); q.pop(); q.push(temp_minc); 67 } 68 else if (minc < res[index])q.pop(); 69 } 70 } 71 } 72 73 int main() { 74 while (scanf_s("%d%d", &n, &m) == 2) { 75 for (int j = 0; j < n; j++)map[j].clear(); 76 memset(d, -1, sizeof(int)*n); 77 while (m--) { 78 scanf_s("%d%d%d", &a, &b, &c); 79 if (a != b) {//我觉得in_q的判断已经去除了自环和重边的问题 80 map[a - 1].push_back(edge(b - 1, c)); 81 map[b - 1].push_back(edge(a - 1, c)); 82 } 83 } 84 re_bfs(); 85 bfs(); 86 printf("%d\n%d", d[0], res[0]); 87 for (int i = 1; i < d[0]; i++)printf("%3d", res[i]); 88 printf("\n"); 89 } 90 }
总结:第一次对图进行bfs操作,其中的困难也是可以想象的,但是念念不忘,必有回响。这次确实收获很多,更加熟悉使用bfs,对图的理解等等,这一切都是建立在实际操作的基础上,所以看完还不自己码一遍吗?
初学算法之uva1599 IdealPath
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。