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
#include
#include
#include
#include
#include
#include
#include
#include
#include

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

*/