首页 > 代码库 > POJ 2449 第k短路
POJ 2449 第k短路
链接：
http://poj.org/problem?id=2449
题意：
给出起点与终点，找出从起点到终点的第k短路，如果起点与终点相同，也要出去走一圈才能算最短路。
题解：
利用A*算法，首先求出其他点到t的最短路径，然后用基于BFS的优先队列A*算法求f(i)=g(i)+h(i)，
其中h(i)表示i到t的最短路，g(i)表示从s到i的路径长度每次取出f(i)值最小的，当第k次取出t时即求出第k短路
代码：
31 int n, m, s, t, k;32 struct edge { int to, cost; };33 vector<edge> G[MAXN];34 vector<edge> rG[MAXN];35 int d[MAXN];36 37 void dijkstra(int s) {38 priority_queue<PII, vector<PII>, greater<PII> > que;39 memset(d, 0x3f, sizeof(d));40 d[s] = 0;41 que.push(mp(0, s));42 while (!que.empty()) {43 PII p = que.top(); que.pop();44 int v = p.second;45 if (d[v] < p.first) continue;46 rep(i, 0, rG[v].size()) {47 edge e = rG[v][i];48 if (d[e.to] > d[v] + e.cost) {49 d[e.to] = d[v] + e.cost;50 que.push(mp(d[e.to], e.to));51 }52 }53 }54 }55 56 struct node {57 int v, c;58 const bool operator<(const node &t) const {59 return c + d[v] > t.c + d[t.v];60 }61 };62 63 int a_star(int s) {64 priority_queue<node> que;65 que.push(node{ s, 0 }); k--;66 while (!que.empty()) {67 node p = que.top(); que.pop();68 int v = p.v;69 if (v == t) {70 if (k) k--;71 else return p.c;72 }73 rep(i, 0, G[v].size()) {74 edge e = G[v][i];75 que.push(node{ e.to,e.cost + p.c });76 }77 }78 return -1;79 }80 81 int main() {82 ios::sync_with_stdio(false), cin.tie(0);83 cin >> n >> m;84 while (m--) {85 int a, b, t;86 cin >> a >> b >> t;87 G[a].pb(edge{ b,t });88 rG[b].pb(edge{ a,t });89 }90 cin >> s >> t >> k;91 dijkstra(t);92 if (d[s] == INF) cout << -1 << endl;93 else {94 if (s == t) k++;95 cout << a_star(s) << endl;96 }97 return 0;98 }
POJ 2449 第k短路
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。