A*K短路模板，详见https://blog.csdn.net/z_mendez/article/details/47057461

算法流程：

把有向图全建成反向边，跑一遍所有点到t的最短路记为dis；

A*，估价函数：g（已走过价值）是已走过的路长度，h（到终点价值估计）是到目的地的最短路，建一个小根堆按h+g排序，每次取出一个点，如果是t点则把g加入答案（注意t点也可以扩展，这里不要continue）；每当一个点出队次数大于k则不再用它扩展（没有价值了）

#include<iostream>

#include<cstdio>

#include<queue>

#include<cstring>

using namespace std;

const int N=10005;

const long long inf=1e15;

int n,m,k,s,t,h[N],cnt,x[N],y[N],z[N],c[N];

long long dis[N],ans[N];

bool v[N];

struct qwe

{

	int ne,to,va;

}e[N];

struct dian

{

	int x;

	long long g,h;//g是已走过的路，h是到目的地的最短路

	dian(int X=0,long long G=0,long long H=0)

	{

		x=X,g=G,h=H;

	}

	bool operator < (const dian &a) const

	{

		return g+h>a.g+a.h;//priority是大根堆，把小于重载成大于相当于改成小根堆

	}

};

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p>'9'||p<'0')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v,int w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

void aster()

{

	priority_queue<dian>q;

	for(int i=1;i<=k;i++)

		ans[i]=-1;

	q.push(dian(n,0,dis[n]));

	int tot=0;

	while(!q.empty())

	{

		int u=q.top().x;

		long long g=q.top().g;

		q.pop();

		c[u]++;

		if(c[u]>k)

			continue;//如果当前点第k次出队,则当前点已经不能给前k短路贡献了

		if(u==1)

			ans[++tot]=g;

		if(c[1]==k)

			return;

		for(int i=h[u];i;i=e[i].ne)

			q.push(dian(e[i].to,g+e[i].va,dis[e[i].to]));

	}

}

int main()

{

	n=read(),m=read(),k=read();

	for(int i=1;i<=m;i++)

	{

		x[i]=read(),y[i]=read(),z[i]=read();

		if(x[i]<y[i])

			swap(x[i],y[i]);

		add(y[i],x[i],z[i]);

	}

	queue<int>q;

	for(int i=1;i<=n;i++)

		dis[i]=inf;

	dis[1]=0,v[1]=1,q.push(1);

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		v[u]=0;

		for(int i=h[u];i;i=e[i].ne)

			if(dis[e[i].to]>dis[u]+e[i].va)

			{

				dis[e[i].to]=dis[u]+e[i].va;

				if(!v[e[i].to])

					v[e[i].to]=1,q.push(e[i].to);

			}

	}

	memset(h,0,sizeof(h));

	cnt=0;

	for(int i=1;i<=m;i++)

		add(x[i],y[i],z[i]);

	aster();

	for(int i=1;i<=k;i++)

		printf("%lld\n",ans[i]);

	return 0;

}