luogu P2939 [USACO09FEB]Revamping Trails G 分层最短路

#include<map>
#include<queue>
#include<stack>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
template<typename int_t>//据说可以自动判断输入的类型
void read(int_t& x)
{
	x=0; int_t k=1; char ch=0;
	while(ch<'0'||ch>'9') {ch=getchar();if(ch=='-') k=-1;}
	while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();}
	x*=k;
}
const int N=4200010;
int e[N],ne[N],w[N],idx,h[N];
int vis[N],dist[N];
int n,m,k;
int a,b,c;
void add(int a,int b,int c)
{
	e[idx]=b;
	w[idx]=c;
	ne[idx]=h[a];
	h[a]=idx++;
 } 
void dijkstra()
{
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;
	memset(vis,0,sizeof vis);
	priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > points;
	points.push(make_pair(0,1));
	while(!points.empty())
	{
		int u=points.top().second;
		points.pop();
		if(!vis[u])
		{
			vis[u]=1;
			for(int i=h[u]; ~i; i=ne[i])
			{
				int to=e[i];
				if(dist[to]>dist[u]+w[i])
				{
					dist[to]=dist[u]+w[i];
					points.push(make_pair(dist[to],to));
				}
			}
		}
	}
}
int main()
{
	memset(h,-1,sizeof h);
	cin>>n>>m>>k;
	for(int i=1; i<=m; i++)
	{
		cin>>a>>b>>c;
		add(a,b,c);
		add(b,a,c);
		for(int j=1; j<=k; j++)
		{
			add(a+(j-1)*n,b+j*n,0);
			add(b+(j-1)*n,a+j*n,0);
			add(a+j*n,b+j*n,c);
			add(b+j*n,a+j*n,c);
		}
	}
	dijkstra();
	int ans=dist[n];
	for(int i=1;i<=k;i++)
		ans=min(ans,dist[n+i*n]);
	cout<<ans<<endl;
	return 0;
}