18分蒟蒻求助

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<iomanip>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<vector>
#include<sstream>
#include<cctype>
#include<map>
#include<set>
#include<stack>
#include<queue>
#include<ctime>
#define ll long long
#define ull unsigned long long
#define ff first
#define ss second
#define rep(i,a,b) for(ll i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const ll INF=2147483647;
inline ll read()
{
	ll x=0,k=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')k=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*k;
}
struct edge{
	ll u,v,w,next;
}e[1008886];
ll head[1008886],n,m,k,x,y,t,num,dis[1008886];
bool vis[1008886];
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,greater<pair<ll,ll> > >q;
void store(ll u,ll v,ll w)
{
	e[++num].u=u,e[num].v=v,e[num].w=w;
	e[num].next=head[u];
	head[u]=num;
}
void dijkstra()
{
	memset(vis,false,sizeof(vis));
	rep(i,1,n*(k+1))dis[i]=INF;
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty())
	{
		ll s=q.top().ss;
		q.pop();
		if(!vis[s])
		{
			vis[s]=true;
			for(ll i=head[s];i;i=e[i].next)
			{
				dis[e[i].v]=min(dis[e[i].v],dis[s]+e[i].w);
				q.push(make_pair(dis[e[i].v],e[i].v));
			}
		}
	}
}
int main()
{
	n=read(),m=read(),k=read();
	rep(i,1,m)
	{
		x=read(),y=read(),t=read();
		store(x,y,t);
		store(y,x,t);
	}
	rep(i,1,k)
	{
		rep(u,1,n)
		{
			for(ll j=head[u];j;j=e[j].next)
			{
				int v=e[j].v;
				store(u+n*(i-1),v+n*i,0);
			}
		}
	}
	dijkstra();
	printf("%lld",dis[n*(k+1)]);
	return 0;
}