#include<stdio.h>
#include<iostream>
#include<queue>
#include<vector>
using namespace std;
#define inf 99999999
#define N 1100
typedef struct nnn
{
int F,G,s;
friend bool operator<(nnn a,nnn b)
{
return a.F>b.F;
}
}PATH;
typedef struct nn
{
int v,w;
}node;
vector<node>map[N],tmap[N];
int H[N];
void SPFA(int s)
{
queue<int>q;
int inq[N]={0};
q.push(s); inq[s]=1; H[s]=0;
while(!q.empty())
{
s=q.front(); q.pop(); inq[s]=0;
int m=tmap[s].size();
for(int i=0;i<m;i++)
{
int j=tmap[s][i].v;
if(H[j]>tmap[s][i].w+H[s])
{
H[j]=tmap[s][i].w+H[s];
if(!inq[j])
inq[j]=1,q.push(j);
}
}
}
}
int Astar(int st,int end,int K)
{
priority_queue<PATH>q;
PATH p,tp;
int k[N]={0};
SPFA(end);
if(H[st]==inf)return -1;
p.s=st; p.G=0; p.F=H[st];
q.push(p);
while(!q.empty())
{
p=q.top(); q.pop();
k[p.s]++;
if(k[p.s]>K)continue;//每个点最多走K次，超过K条路不必走
if(p.s==end&&k[end]==K) return p.F;
int m=map[p.s].size();
for(int i=0;i<m;i++)
{
int j=map[p.s][i].v;
if(H[j]!=inf)//表明当前点不能通向终点，就不用加入队列
{
tp.G=p.G+map[p.s][i].w;
tp.F=H[j]+tp.G;
tp.s=j;
q.push(tp);
}
}
}
return -1;
}
int main()
{
int n,m,S,T,K,a,b,t;
node p;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
map[i].clear(); tmap[i].clear(); H[i]=inf;
} while(m--)
{
scanf("%d%d%d",&a,&b,&t);
p.v=b; p.w=t; map[a].push_back(p);
p.v=a; tmap[b].push_back(p);//反建一个地图求H
}
scanf("%d%d%d",&S,&T,&K);
if(S==T)K++;
printf("%d\n",Astar(S,T,K));
}
POJ2449
图论模板题，题意是给你起点A和终点B，求A到B的第K条最短路。
输入M，N（M个点，N条边）
输入S,E,T（S起始点，E终点，T代表第T条最短路）
输出第T条最短路的长度，如果没有，则输出-1.
思路：由单源最短路径可求得各点到E的距离，利用估价函数=当前长短的实际代价（起点到点K）+估计代价（点K到终点）
可得Astar优先队列保存节点求出最终结果，纯模板题。
另外题目用的Astar算法即是启发式搜索，类似与穷举，但在穷举的途中进行大量优化（因为前期已经做了单源路径最短化处理），减少不必要的搜索，利用起点，中间点，终点之间的估价关系进行求解。
算法与实现上的模板没用，有点复杂。