链接：http://poj.org/problem?id=2449
题意：告诉你有n个顶点，m条边，并把这些边的信息告诉你：起点、终点、权值，再告诉你s、t、k，需求出s到t的第k短路，没有则输出-1。
第K短路裸题，A*算法没接触过，参考了这篇博客：http://www.cnblogs.com/n-u-l-l/archive/2012/07/29/2614194.html
以下大体字摘自这篇博文，讲的很清楚：
对于第k短路，可以想到的一个比较朴素的算法就是广度优先搜索，使用优先队列从源点s进行广搜，当第k次搜索到终点t时，所得长度即所求但是这种方法在运行过程中会产生特别多的状态，当图比较简单、k比较小时，可以一试，但是当k较大或者图中点数较多时，会面临爆栈的危险。
目前使用比较多的算法是单源最短路配合A*。A*是搜索中比较高级的方式，A*算法结合了启发式方法（这种方法通过充分利用图给出的信息来动态的作出决定而使搜索次数大大降低）和形式化方法（这种方法不利用图给出的信息，而仅通过数学的形式分析，如Dijkstra算法）。
它通过一个估价函数f(h)来估计图中的当前点p到终点的距离，并由此决定它的搜索方向，当这条路径失败时，它会尝试其他路径。对于A*，估价函数=当前值+当前位置到终点的距离，即f(p)=g(p)+h(p)，每次扩展估价函数值最小的一个。对于第k短路算法来说，g(p)为从源点s到当前点p所走的路径长度，h(p)为从当前点p到终点t的最短路，因此f(p)的意义就是从s按照当前路径经过p点后到达t的总距离。也就是每次扩展都是有方向的，这样无论对提高出解的速度还是降低扩展的状态数目都是有好处的。为了加快计算，h(p)需要在搜索之前进行预处理，只要将原图的所有边反向，再从终点t做一次单源最短路即可得到h(p)。单源最短路求法有Dijkstra，Bellman-Ford，SPFA等。
具体步骤：
这里我们使用链式前向星来存储如图，由于需要预处理所有点到终点的最短路，就需要将图G中所有边反向得到图G'，再从终点t做一次单源最短路，所以实际上就是两张图。
（1）将有向图的所有边反向（无向图可以省略此步），以原图终点t为源点做一次单源最短路，结果记入数组dis[i]中，dis[i]即为原图中点i到点t的最短距离。这里的dis[i]即上述的h(p);
（2）新建一个优先队列，将源点s加入到队列中；
（3）从优先队列中弹出f(p)最小的点p（这里如果存在f(p)相等的点，则弹出g(p)最小的点），如果点p就是终点t，则计算t出队列的次数，如果当前为t的第k次出队，则当前路径长度就是s到t的第k短路，算法结束；否则遍历与p相连的所有的边，将扩展出的到p的邻接点信息加入到优先队列。
值得注意的是，当s==t时需要计算(k+1)短路，因为s到t这条距离为0的路不能算在这k短路中，这时只需将k自增1后再求第k短路即可。
这道题比较坑的地方就是上面说的 s==t时需要计算（k+1）短路，m==0时也即s==t时，k+1短路不存在，应输出-1，还有就是dist[s]！=INF时，虽然A*能找到最短路，但如果k较大，不一定存在第k短路，所以应当有个标记，我忘记加标记多WA了一发
#include<cstring>
#include<string>
#include<fstream>
#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cctype>
#include<algorithm>
#include<queue>
#include<map>
#include<set>
#include<vector>
#include<stack>
#include<ctime>
#include<cstdlib>
#include<functional>
#include<cmath>
using namespace std;
#define PI acos(-1.0)
#define MAXN 100100
#define eps 1e-7
#define INF 0x7FFFFFFF
#define seed 131
#define ll long long
#define ull unsigned ll
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
struct NODE{
int u;
int f,g;
bool operator < (const NODE &t) const{
if(t.f==f) return t.g > g;
return t.f < f;
}
};
struct EDGE{
int u,w,next;
};
struct NODE2{
int u,dis;
bool operator < (const NODE2 &t) const{
return t.dis < dis;
}
};
EDGE edge[MAXN],redge[MAXN];
int head[1010],rhead[1010],vis[1010],dist[1010];
int n,m,cnt,rcnt,ans,flag;
void add_edge(int a,int b,int c){
edge[cnt].u = b;
edge[cnt].w = c;
edge[cnt].next = head[a];
head[a] = cnt++;
redge[rcnt].u = a;
redge[rcnt].w = c;
redge[rcnt].next = rhead[b];
rhead[b] = rcnt++;
}
void dijkstra_heap(int v){
NODE2 t1,t2;
int i,j;
for(i=1;i<=n;i++) dist[i] = INF;
dist[v] = 0;
t1.u = v;
t1.dis = 0;
priority_queue<NODE2>q;
q.push(t1);
while(!q.empty()){
t1 = q.top();
q.pop();
if(vis[t1.u]) continue;
vis[t1.u] = 1;
for(i=rhead[t1.u];i!=-1;i=redge[i].next){
int x = redge[i].w;
if(dist[t1.u]+x<dist[redge[i].u]){
dist[redge[i].u] = x + dist[t1.u];
t2.dis = dist[redge[i].u];
t2.u = redge[i].u;
q.push(t2);
}
}
}
}
void Astar(int s,int t,int k){
int i,j=0;
NODE t1,t2;
priority_queue<NODE>q;
t1.u = s;
t1.g = 0;
t1.f = t1.g + dist[s];
q.push(t1);
while(!q.empty()){
t1 = q.top();
q.pop();
if(t1.u==t) j++;
if(j==k){
ans = t1.f;
flag = 1; //没加标记，WA出翔
return ;
}
for(i=head[t1.u];i!=-1;i=edge[i].next){
t2.u = edge[i].u;
t2.g = t1.g + edge[i].w;
t2.f = t2.g + dist[t2.u];
q.push(t2);
}
}
}
int main(){
int i,j;
int s,t,k;
int a,b,c;
while(scanf("%d%d",&n,&m)!=EOF){
memset(head,-1,sizeof(head));
memset(rhead,-1,sizeof(rhead));
memset(vis,0,sizeof(vis));
cnt = rcnt = 0;
ans = 0;
flag = 0;
for(i=0;i<m;i++){
scanf("%d%d%d",&a,&b,&c);
add_edge(a,b,c);
}
scanf("%d%d%d",&s,&t,&k);
if(s==t) k++;
dijkstra_heap(t);
if(dist[s]==INF&&m==0){
puts("-1");
continue;
}
Astar(s,t,k);
if(!flag) puts("-1");
else printf("%d\n",ans);
}
return 0;
}