题意就是求第k短路。。
先提醒一下一下不读题的朋友，起点是n，终点是1
特地找的这道题来做
至于怎么找，就是A*
不会A*的朋友不要慌，因为我也不会。。
定义看看就好
f(n)=g(n)+h(n)
f就是估价函数
正确性显然，主要是怎么弄出后面两个
我们从n点出发，当到达i点时
g值就是现在的路程
h值就是他最少还要多少距离才能到终点
当然，我也有疑惑，这个h有什么用啊！
其实你只要想一下，你现在走的远，不一定就不优
但要是我们加上h的话，就知道你现在最好最好的情况要多少了
举个例子：
现在你到了2和3，代价分别是10和100，到1的距离是10000和1000
那你是用2更新更小的答案吗？当然不是！
因为他下一步的代价很大
可能讲得不大清楚，看看代码画画图就好了。。
怎么实现呢
h值可以用SPFA预处理
然后g值在第一次的时候跑就好了，用dij
时间复杂度O(nk)其实我觉得要套多一个log，因为要用有点队列维护
贴个板子吧：
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<queue>
typedef long long LL;
using namespace std;
const LL N=1005;
const LL M=10005;
LL n,m,k;
struct qq{LL x,y,z,last;}s[M],s1[M];
LL num,last[N];
LL num1,last1[N];
void init (LL x,LL y,LL z)
{num++;s[num].x=x;s[num].y=y;s[num].z=z;s[num].last=last[x];last[x]=num;swap(x,y);num1++;s1[num1].x=x;s1[num1].y=y;s1[num1].z=z;s1[num1].last=last1[x];last1[x]=num1;
}
LL h[N];//起点到这里的最短距离 准确点来说，是这里到起点的最短距离
bool in[N];
void SPFA ()
{queue<int> q;memset(in,false,sizeof(in));memset(h,127,sizeof(h));q.push(1);in[1]=true;h[1]=0;while (!q.empty()){LL x=q.front();q.pop();for (LL u=last1[x];u!=-1;u=s1[u].last){LL y=s1[u].y;if (h[y]>h[x]+s1[u].z){h[y]=h[x]+s1[u].z;if (in[y]==false){in[y]=true;q.push(y);}}}in[x]=false;}return ;
}
struct qt
{LL g,h,x;bool operator < (qt a) const{return a.g+a.h<g+h;};
};
LL ans[N];
LL cnt[N];
void Astar ()
{memset(cnt,0,sizeof(cnt));priority_queue<qt> q;qt a,b;a.x=n;a.g=0;a.h=h[n];q.push(a);LL size=0;while (!q.empty()){a=q.top();q.pop();// printf("%lld %lld\n",a.x,a.g);cnt[a.x]++;if (cnt[a.x]>k) continue;if (a.x==1) ans[++size]=a.g;if (cnt[1]>=k) return ;for (LL u=last[a.x];u!=-1;u=s[u].last){LL y=s[u].y;b.x=y;b.g=a.g+s[u].z;b.h=h[y];q.push(b);}}return ;
}
int main()
{num=0;memset(last,-1,sizeof(last));num1=0;memset(last1,-1,sizeof(last1));scanf("%lld%lld%lld",&n,&m,&k);for (LL u=1;u<=m;u++){LL x,y,z;scanf("%lld%lld%lld",&x,&y,&z);if (x<y) swap(x,y);init(x,y,z);}SPFA();memset(ans,-1,sizeof(ans));Astar();for (LL u=1;u<=k;u++) printf("%lld\n",ans[u]);return 0;
}