1.到底如何求k短路的？
我们考虑，要求k短路，要先求出最短路/次短路/第三短路……/第(k-1)短路，然后访问到第k短路。
接下来的方法就是如此操作的。
2.f(x)的意义？
我们得到的f(x)更小，优先访问这个f(x)的点。
我们可以定义一组数{p,g,h}，p是某一个点，g是估价，h是实际，那么g+h更小的点p会优先访问。
为什么呢？因为假设我们求出了w短路，接下来要求(w+1)短路，就要求最小的另一条路径。
应该易理解。
3.为什么选择最短路来估价？
很简单的选择，我们既然要求最短了，当然是找最短路。
事实上这不是我们的初衷，但是有了“先求(k-1)短路”的概念后，这么理解也可以了。
4.实现
实现是比较简单的。
如何预处理出g(x)呢？显然，将所有边反向，然后求end到所有点的单源最短路径就好了。
接下来的启发式搜索可以简单解决。
事实上，就是在暴力搜索的基础上增加了启发式搜索：往一个最优的点的地方走。
另外还是要专来一篇这题blog的QAQ
关于上题目的程序：
86ms
#include<iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
using namespace std;
const int N=+;
const int inf=0x3f3f3f3f;
struct edge
{
int u,v,w,next;
}e[N<<];
int head[N<<],head1[N<<],dis[N<<],vis[N<<],cnt[N<<];
int num;
int n,m;
int s,t,k;
struct node
{
int g,h;
int to;
bool operator<(node a)const
{
return a.h+a.g<h+g;
}
};
void init()
{
num=;
memset(head1,-,sizeof(head1));
memset(head,-,sizeof(head));
}
void addegde(int u,int v,int w)
{
e[num].v=v;
e[num].w=w;
e[num].next=head[u];
head[u]=num++;
e[num].v=u;
e[num].w=w;
e[num].next=head1[v];
head1[v]=num++;
}
void spfa()
{
memset(vis,,sizeof(vis));
memset(dis,inf,sizeof(dis));
dis[t]=;
vis[t]=;
queue<int>q;
q.push(t);
while(!q.empty())
{
int u=q.front();
q.pop();
vis[u]=;
for(int i=head1[u];i!=-;i=e[i].next)
{
int v=e[i].v;
if(dis[v]>dis[u]+e[i].w)
{
dis[v]=dis[u]+e[i].w;
if(!vis[v])
{
q.push(v);
vis[v]=;
}
}
}
}
}
int AA()
{
memset(cnt,,sizeof(cnt));
priority_queue<node>Q;
node p,q;
p.g=;
p.to=s;
p.h=dis[s];
Q.push(p);
while(!Q.empty())
{
q=Q.top();
Q.pop();
cnt[q.to]++;
if(cnt[q.to]>k)
continue;
if(cnt[t]==k)
return q.g;
for(int i=head[q.to];i!=-;i=e[i].next)
{
int v=e[i].v;
p.to=v;
p.g=q.g+e[i].w;
p.h=dis[v];
Q.push(p);
}
}
return -;
}
int main()
{
while(~scanf("%d%d%d",&n,&m,&k))
{
scanf("%d%d",&s,&t);
init();
for(int i=;i<m;i++)
{
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
addegde(u,v,w);
} spfa();
if(s==t)k++;
//cout<<dis[s]<<endl;
int ans=AA();
printf("%d\n",ans);
}
return ;
}
SPFA+A*