A*算法求第k短路流程：
1）计算h[]，即当前点到t的估计值
若为有向图，建立反向图求出h[]。若为无向图，可直接求解h[]。可通过SPFA求解。
2）A*搜索
每次找到新节点就直接加入队列，计算出估价函数f[]=g[]+h[]，然后加入优先队列中。（此步不可优化，否则可能造成失解）
常用STL priority_queue实现，要注意默认是大根堆，可重载<实现小根堆。
3）若根入队k次，返回
ADD：
该题几个注意事项及优化：
a）若起始点h值==INF，不搜。
b）若一个点入队超过k次，不搜。
c）邻接表代替邻接矩阵，防止重边。
d）该题中若s==t，距离为0的路径不能计入。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <cmath>
#include <utility>
#include <vector>
#include <queue>
#include <map>
#include <set>
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define INF 0x3f3f3f3f
#define N 1005
#define M 100005 using namespace std; struct Edge
{
int y,w,ne;
}e[M*],re[M*]; int x,y,w,n,m,s,t,k;
int be[N],all;
int rbe[N],rall;
int h[N],cnt[N];
bool vis[N]; struct Point
{
int x,g;
bool operator < (const Point T) const
{
return g+h[x]>T.g+h[T.x];
}
}; void add(int x, int y, int w)
{
e[all].y=y;
e[all].w=w;
e[all].ne=be[x];
be[x]=all++;
}
void radd(int x, int y, int w)
{
re[rall].y=y;
re[rall].w=w;
re[rall].ne=rbe[x];
rbe[x]=rall++;
} void SPFA(int s)
{
queue< int > q;
while(!q.empty())
q.pop();
for(int i=; i<=n; i++)
{
h[i]=INF;
vis[i]=;
}
h[s]=;
vis[s]=;
q.push(s);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=;
for(int i=rbe[u]; i!=-; i=re[i].ne)
{
int v=re[i].y;
if(h[v]>h[u]+re[i].w)
{
h[v]=h[u]+re[i].w;
if(!vis[v])
{
vis[v]=;
q.push(v);
}
}
}
}
} int Astar(int s, int t, int k)
{
SPFA(t);
if(h[s]==INF) return -;
priority_queue< Point > q;
while(!q.empty())
q.pop();
memset(vis,,sizeof(vis));
memset(cnt,,sizeof(cnt));
Point cur,nxt;
cur.x=s;
cur.g=;
q.push(cur);
while(!q.empty())
{
cur=q.top();
q.pop();
if((++cnt[cur.x])>k) continue;
if(cnt[t]==k)
return cur.g;
for(int i=be[cur.x]; i!=-; i=e[i].ne)
{
nxt.x=e[i].y;
nxt.g=cur.g+e[i].w;
q.push(nxt);
}
}
return -;
} void init()
{
all=;
memset(be,-,sizeof(be));
rall=;
memset(rbe,-,sizeof(rbe));
} int main()
{
scanf("%d%d",&n,&m);
init();
for(int i=; i<m; i++)
{
scanf("%d%d%d",&x,&y,&w);
add(x,y,w);
radd(y,x,w);
}
scanf("%d%d%d",&s,&t,&k);
if(s==t) k++;
printf("%d\n",Astar(s,t,k));
return ;
} /* 2 4
1 2 1
1 2 2
1 2 3
2 1 5
1 2 5 */