POJ 2449 A*K短路

本文主要是介绍POJ 2449 A*K短路，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A*搜索算法的优越之处在于它能够更快地得到结果。
A*求解K短路的思想就像是dijkstra求最短路的加强版。我们预估每个点到终点的距离为它们到终点的最短路径并以估计值与当前实际值作为标准量入堆。这样子可以避免极端情况：小的不停的被扩展，大的很少被扩展的情况。A* 算法 的估价函数是程序速度的保证， 估价函数的选取必须仔细思考，这类问题可以多做题积累经验。

%:pragma GCC optimize(3)
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<queue>
using namespace std;const int N = 1005;
const int M = 100005 * 2;int fir[N] , ne[M] , to[M] , C[M] , dis[N] , cnt = 1 , st ,en , k , n , m , x , y , z;
vector<int>G[N];
vector<int>Val[N];void add(int x ,int y ,int z) {ne[++ cnt] = fir[x];fir[x] = cnt;to[cnt] = y;C[cnt] = z;G[y].push_back(x);Val[y].push_back(z);
}#define Foreachson(i,x) for(int i = fir[x];i;i = ne[i])bool inq[N];void SPFA(int s) {queue<int>q;memset(dis,127,sizeof(dis));dis[s] = 0;inq[s] = 1;q.push(s);while(!q.empty()) {int ind = q.front();q.pop();inq[ind] = 0;for(int i = 0; i <(int) G[ind].size(); i ++) {int V = G[ind][i];if(dis[V] > dis[ind] + Val[ind][i]) {dis[V] = dis[ind] + Val[ind][i]; if(!inq[V]) {inq[V] = 1;q.push(V);}}}}
}int H[N] , tot;struct NODE {int h ,  g , f,  no;void make(int x ,int y ,int s) {h = x; g = y;f = x + y;no = s;}friend bool operator < (NODE xxx , NODE yyy) {return xxx.f > yyy.f;}
}id , tmp;priority_queue<NODE>q;int Astar(int s , int t) {if (s == t) k ++;if(H[s] > 2e9) return -1;id.make(0 , H[s] , s);q.push(id);while(!q.empty()) {tmp = q.top(); q.pop();int ind = tmp.no;if(ind == t) {tot ++;
//          cout<<tmp.h<<endl;if(tot == k) return tmp.h;}Foreachson(i,ind) {int V = to[i];id.make(tmp.h + C[i] , H[V] , V);q.push(id);}}return -1;
}int main() {scanf("%d%d",&n,&m);for(int i = 1; i <= m; i ++) {scanf("%d%d%d",&x,&y,&z);add(x,y,z);}scanf("%d%d%d",&st,&en,&k);SPFA(en);for(int i = 1;i <= n;i ++) H[i] = dis[i]; printf("%d\n",Astar(st,en));
}

显然，终点第k次出堆即是答案。

这篇关于POJ 2449 A*K短路的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---