本文主要是介绍Ideal Path（UVA 1599），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
网址如下：
Ideal Path - UVA 1599 - Virtual Judge (vjudge.net)
（第三方网站）
写了超久，最后是TLE，实在是累了，先总结一下吧
最后是对bfs有了个更深刻的理解
bfs相当于分层次进行分析处理，所以可以用队列来实现
如果想要将层次分开进行处理的话，可以用两个类似队列的东西（比如数组），然后分成两层判断，慢慢进行下去
我的代码主要是在寻找最小的颜色上花的时间很多
代码如下：
#include<cstdio>
#include<queue>
#include<cstring>
#include<set>
#include<map>
#include<vector>
using namespace std;
struct Point{int d;map<int, int> p;map<int, set<int>> mclr;Point():d(0){}
};
void initialize(void);
void bfs1(void);
void bfs2(void);
const int maxn = 100001, maxclr = 1000000001;
int n, m, minstep;
Point pit[maxn];int main(void)
{while(scanf("%d%d", &n, &m) == 2){initialize();for(int i = 0; i < m; i++){int a, b, c; scanf("%d%d%d", &a, &b, &c);pit[a].p[b] = c; pit[b].p[a] = c;}bfs1();bfs2();//同时输出}return 0;
}void initialize(void)
{minstep = 2147483647;for(int i = 1; i <= n; i++){pit[i].d = 0; pit[i].p.clear();}
}
void bfs1(void)
{queue<int> q; q.push(n);while(!q.empty()){int u = q.front(); q.pop();if(u == 1) minstep = pit[u].d;if(pit[u].d >= minstep) continue;for(auto v = pit[u].p.begin(); v != pit[u].p.end(); v++){if((*v).first != n && !pit[(*v).first].d){pit[(*v).first].d = pit[u].d + 1;pit[(*v).first].mclr[pit[u].d].insert(pit[(*v).first].p[u]);q.push((*v).first);}}}
}
void bfs2(void)
{printf("%d\n", minstep);vector<int> q; q.push_back(1);vector<int> ans; ans.resize(minstep, maxclr);while(!q.empty()){int minclr = maxclr, goalD = pit[q.front()].d - 1;for(auto it = q.begin(); it != q.end(); it++){int clr = *(pit[*it].mclr[goalD].begin());minclr = (minclr < clr) ? minclr : clr;}//得到当前层数到下一层的最小颜色ans[pit[q.front()].d - 1] = minclr;//储存答案if(!goalD) break;queue<int> tq;//下一层队列while(!q.empty()){int u = q.back(); q.pop_back();//将目标传到下一层队列for(auto it = pit[u].p.begin(); it != pit[u].p.end(); it++){if(pit[it->first].d == goalD && it->second == minclr) tq.push(it->first);}}//将下一层队列复制到当前队列中while(!tq.empty()){q.push_back(tq.front()); tq.pop();}}//输出while(minstep){printf("%d", ans[--minstep]);if(minstep) putchar(' ');}putchar('\n');
}这篇关于Ideal Path（UVA 1599）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
