记录编号	590700	评测结果	AAAAAAAAAA
题目名称	行动！行动！	最终得分	100
用户昵称	彭欣越	是否通过	通过
代码语言	C++	运行时间	0.394 s
提交时间	2024-07-10 17:21:10	内存使用	15.37 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,k,S,T,tot=0,mk[2000010],dp[5000010];
struct node {
    int idx,val,nxt,hd;
}e[5000010];
void add (int u,int v,int w) {
    e[++tot].idx=v;
    e[tot].val=w;
    e[tot].nxt=e[u].hd;
    e[u].hd=tot;
}
struct edge {
	int u,dis;
	bool operator<(const edge&o) const {
		return o.dis<dis;
	}
};
priority_queue<edge>q;
void dijkstra () {
    for(int i=0;i<=1000000;i++){
        dp[i]=1e9;
    }
    q.push(edge{S,0});
    dp[S]=0;
    while (q.size()) {
        edge t=q.top();
        q.pop();
        if (mk[t.u]) continue;
        mk[t.u]=1;
        for (int i=e[t.u].hd;i;i=e[i].nxt) {
            int v=e[i].idx,w=e[i].val;
            if (dp[v]>dp[t.u]+w) {
                dp[v]=dp[t.u]+w;
                q.push((edge){v,dp[v]});
            }
        }
    }
}
int main () {
    freopen("move.in","r",stdin);
    freopen("move.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m >> k;
    cin >> S >> T;
    for (int i=1;i<=m;i++) {
        int a,b,c;
        cin >> a >> b >> c;
        add(a,b,c);
        add(b,a,c);
        for(int j=1;j<=k;j++){
			add(j*n+a,j*n+b,c);
			add(j*n+b,j*n+a,c);
			add((j-1)*n+a,j*n+b,0);
			add((j-1)*n+b,j*n+a,0);
		}
    }
    dijkstra();
    int res=2147483647;
	for(int i=0;i<=k;i++){
		res=min(res,dp[i*n+T]);
	}
	cout << res <<endl;
    return 0;
}