// Problem: P4822 [BJWC2012]冻结
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4822
// Memory Limit: 125 MB
// Time Limit: 3000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// author:zymooll

#include<bits/stdc++.h>
#define int long long
#define getchar getchar_unlocked
using namespace std;
int read(){
	int f=1,x=0;
	char c=getchar();
	while(c>'9'||c<'0'){
		if(c=='-')f=-1;
		c=getchar();
	}
	while(c>='0'&&c<='9'){
		x=x*10+c-'0';
		c=getchar();
	}
	return x*f;
}
void write(int x){
	if(x<0){
		putchar('-');
		x=-x;
	}
	if(x>10)write(x/10);
	putchar(x%10+'0');
	return;
}
int n,m,k;
int cut,head[3010];
int dis[3010];
priority_queue<pair<int,int> >q;
struct Edge{
	int v,w,next;
}edge[220010];
void add_edge(int u,int v,int w){
	cerr<<u<<" "<<v<<" "<<w<<" "<<endl;
	edge[++cut].v=v;
	edge[cut].w=w;
	edge[cut].next=head[u];
	head[u]=cut;
}
signed main(){
	memset(dis,0x7f,sizeof(dis));
	cin>>n>>m>>k;
	for(int i=1;i<=n;i++){
		int u,v,w;
		u=read(),v=read(),w=read();
		add_edge(u,v,w);
		add_edge(v,u,w);
		for(int j=1;j<=k;j++){
			add_edge(u+j*n,v+j*n,w);
			add_edge(v+j*n,u+j*n,w);
			add_edge(u+(j-1)*n,v+j*n,w/2);
			add_edge(v+(j-1)*n,u+j*n,w/2);
		}
	}
	dis[1]=0;
	q.push(make_pair(0,1));
	while(!q.empty()){
		int u=q.top().second;
		q.pop();
		for(int i=head[u];i;i=edge[i].next){
			int v=edge[i].v,w=edge[i].w;
			if(dis[u]+w<dis[v]){
				dis[v]=dis[u]+w;
				q.push(make_pair(-dis[v],v));
			}
		}
	}
	int ans=INT_MAX;
	for(int i=0;i<=k;i++){
		ans=min(ans,dis[n+n*i]);
	}
	cout<<ans;
	return 0;
}

分层图做法 #1 #4 #7 AC #2 #6 TLE #3 #5 #8 #9 #10 WA 30pts求助