启发函数:f(x)=g(x)+h(x);
g(x)表示初始点到x状态的代价，h(x)表示从x的状态到目标状态的代价的估计值（并不是真实的）,实际最小代价<=h(x);
起点s,终点t，x.v=s,x.len=0;然后优先队列中f(x)值最小值出队列，再根据出队列的x.v状态发展下一层。如果出队列时第一次遇到x.v==t,
就找到了s到t的最短路。...如果第k次，那就是第k短。为了加速计算,h(p)需要在A*搜索之前进行预处理,只要将原图的所有边反向,
再从终点t做一次单源点最短路径就能得到每个点的h(p)了;
其实到现在可以发现，如果g(x)为0，那么求出来的就是最短路系列，如果h(x)为0，求出来的就是BFS最少次数。
#include<stdio.h> #include<string.h> #include<queue> #define INF 99999999 using namespace std; const int maxn = 1100; struct Enode { int to; int val; int next; }edge1[100100],edge2[100100]; struct node { int to; int g,f;//g别的点到此状态的代价 f启发函数 friend bool operator<(node a,node b){ if(a.f!=b.f) return a.f>b.f; return a.g>a.g; } }; int n,dis[maxn],pre1[maxn],pre2[maxn],index1,index2; void init() { index1=index2=1; memset(pre1,-1,sizeof(pre1)); memset(pre2,-1,sizeof(pre2)); } void add1(int x,int y,int z) { edge1[index1].to=y; edge1[index1].val=z; edge1[index1].next=pre1[x]; pre1[x]=index1++; } void add2(int x,int y,int z) { edge2[index2].to=y; edge2[index2].val=z; edge2[index2].next=pre2[x]; pre2[x]=index2++; } void spfa(int s) { queue<int>q; int vis[maxn],i,j; for(i=0;i<=n;i++) { vis[i]=0; dis[i]=INF; } dis[s]=0; vis[s]=1; q.push(s); while(!q.empty()) { int t=q.front(); q.pop(); vis[t]--; if(vis[t]>n) break; for(i=pre2[t];i!=-1;i=edge2[i].next) { if(dis[edge2[i].to]>dis[t]+edge2[i].val) { dis[edge2[i].to]=dis[t]+edge2[i].val; q.push(edge2[i].to); } } } } int A_star(int s,int t,int k) { node temp; priority_queue<node>q; int cnt=0; if(s==t) k++; if(dis[s]==INF) return -1; temp.to=s; temp.g=0; temp.f=temp.g+dis[temp.to]; q.push(temp); while(!q.empty()) { temp=q.top(); q.pop(); if(temp.to==t) { cnt++; } if(cnt==k) { return temp.g; } for(int i=pre1[temp.to];i!=-1;i=edge1[i].next) { node tt; tt.to=edge1[i].to; tt.g=temp.g+edge1[i].val; tt.f=tt.g+dis[tt.to]; q.push(tt); } } return -1; } int main() { int i,j,m; while(~scanf("%d%d",&n,&m)) { init(); for(i=0;i<m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add1(x,y,z);//原图 add2(y,x,z);//反向图 } int s,t,k; scanf("%d%d%d",&s,&t,&k); spfa(t); int ans=A_star(s,t,k); printf("%d ",ans); } }