73pts求调,WA on#3 #4 #8

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,k;
const int maxn = 1e6 + 5;
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
bool vis[maxn];
int dis[maxn],head[maxn],tot,s,t;
struct node
{
	int to,next,cost;
}e[maxn];
void add(int u,int v,int w)
{
	e[++tot].to = v;
	e[tot].cost = w;
	e[tot].next = head[u];
	head[u] = tot;
}
void dij(int s)
{
	memset(dis,0x3f3f3f3f,sizeof(dis));
	dis[s] = 0;
	q.push(make_pair(0,s));
	while(!q.empty())
	{
		int u = q.top().second;
		q.pop();
		if(vis[u]) continue;
		vis[u] = 1;
		for(int i = head[u];i;i = e[i].next)
		{
			int y = e[i].to,z=e[i].cost;
			if(dis[y] > dis[u] + z)
			{
				dis[y] = dis[u] + z;
				q.push(make_pair(dis[y],y));
			}
		}
	}
}
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);
	cin >> n >> m >> k >> s >> t;
	for(int i = 1;i <= m;i++)
	{
		int u,v,c;
		cin >> u >> v >> c;
		add(u,v,c);
		add(v,u,c);
		for(int j = 1;j <= k;j++)
		{
			add(u + (j - 1) * n,v + j * n,0);
			add(v + (j - 1) * n,u + j * n,0);
			add(u + j * n,v + j * n,c);
			add(v + j * n,u + j * n,c);
		}
	}
	for(int i = 1;i <= k;i++)
	{
		add(t + (i - 1) * n,t + i * n,0); 
	}
	dij(s);
	cout << dis[t + k*n] << endl;
	return 0;
}