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=100000+10; const int inf=0x3f3f3f3f; struct edge { int u,v,w,next; }e[N<<1]; int head[N<<1],head1[N<<1],dis[N<<1],vis[N<<1],cnt[N<<1]; 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=0; memset(head1,-1,sizeof(head1)); memset(head,-1,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,0,sizeof(vis)); memset(dis,inf,sizeof(dis)); dis[t]=0; vis[t]=1; queue<int>q; q.push(t); while(!q.empty()) { int u=q.front(); q.pop(); vis[u]=0; for(int i=head1[u];i!=-1;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]=1; } } } } } int AA() { memset(cnt,0,sizeof(cnt)); priority_queue<node>Q; node p,q; p.g=0; 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!=-1;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 -1; } int main() { while(~scanf("%d%d%d",&n,&m,&k)) { scanf("%d%d",&s,&t); init(); for(int i=0;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 ",ans); } return 0; }