首页 > 代码库 > Uva 1599 最佳路径
Uva 1599 最佳路径
题目链接：https://uva.onlinejudge.org/external/15/1599.pdf
题意： 保证在最短路的时候，输出字典序最小的路径。
方法：
路径上有了权值，可以利用图论的数据结构来BFS，很方便。
逆序BFS，找到每个点距离终点的最短路长 d[x] ;
然后，从起点，沿着 d[u] = d[v] + 1; 的路径，分层BFS，选字典序最小的。找到那个最小字典序的节点之后，从新建队列。直到找完 d[0];
#include <bits/stdc++.h>using namespace std;const int maxn = 100000 + 5;const int INF = 1000000000;struct Edge{ int u,v,c; Edge(int u=0,int v = 0,int c = 0) : u(u),v(v),c(c) {}};int n,m;vector<Edge> edges;vector<int> G[maxn];void AddEdge(int from,int to,int c){ edges.push_back(Edge(from,to,c)); int idx = edges.size(); G[from].push_back(idx-1);}int d[maxn];bool vis[maxn];vector<int> ans;void rev_bfs(){ memset(vis, 0, sizeof(vis)); d[n-1] = 0; vis[n-1] = true; queue<int> q; q.push(n-1); while(!q.empty()) { int u = q.front(); q.pop(); for(int i = 0; i < G[u].size(); i++) { Edge _edge = edges[G[u][i]]; int v = _edge.v; if(!vis[v]) { vis[v] = true; d[v] = d[u] + 1; q.push(v); } } }}void bfs(){ memset(vis,0,sizeof(vis)); vector<int> next; next.push_back(0); vector<int> ans; for(int i=0; i<d[0]; i++) { int min_color = INF; for(int j=0; j<next.size(); j++) ///队列中一个级别的结点 { int u = next[j]; for(int k=0; k<G[u].size(); k++) { Edge _edge = edges[G[u][k]]; int v = _edge.v; if(d[u]==d[v]+1) min_color = min(min_color,_edge.c); } } ans.push_back(min_color); vector<int> next2; for(int j=0; j<next.size(); j++) { int u = next[j]; for(int k=0; k<G[u].size(); k++) { Edge _edge = edges[G[u][k]]; int v = _edge.v; if(d[u]==d[v]+1&&vis[v]==false&&_edge.c==min_color) { vis[v] = 1; next2.push_back(v); } } } next = next2; } printf("%d\n", ans.size()); printf("%d", ans[0]); for(int i = 1; i < ans.size(); i++) printf(" %d", ans[i]); printf("\n");}int main(){ while(~scanf("%d%d",&n,&m)) { memset(d,0,sizeof(d)); edges.clear(); for(int i=0;i<n;i++) G[i].clear(); for(int i=0; i<m; i++) { int u,v,c; scanf("%d%d%d",&u,&v,&c); u--; v--; AddEdge(u,v,c); AddEdge(v,u,c); } rev_bfs(); bfs(); } return 0;}
Uva 1599 最佳路径
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。