题目
一个无向图，一个路径的代价为经过的边的代价的前(k)大和（不足就全部）。问最短路。
(n,mle 3000)
枚举第(k)大的边权(lim)，把小于(lim)的边连着的点缩起来，大于(lim)的边连上。然后跑恰好(k)长度的最短路。
恰好(k)长度的最短路不好做，可以将每个边权(w)变成(w-lim)，最后加上(lim*k)。
这样不超过(k)长度的边，不足的部分相当于用(lim)长度来补。
时间(O(n(n+m)lg m))
using namespace std;
#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 3010
#define ll long long
#define INF 0x7f7f7f7f7f7f7f7f
int n,m,k;
struct edge{
int u,v,w;
} ed[N];
bool cmped(edge a,edge b){return a.w<b.w;}
struct EDGE{
int to,w;
EDGE *las;
};
struct Graph{
EDGE e[N*2];
int ne;
EDGE *last[N];
void link(int u,int v,int w){
e[ne]={v,w,last[u]};
last[u]=e+ne++;
}
void clear(){
ne=0;
memset(last,0,sizeof(EDGE*)*(n+1));
}
} F;
int fa[N];
int getfa(int x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
ll f[N];
pair<int,ll> h[N*N];
int nh;
bool cmph(pair<int,ll> a,pair<int,ll> b){
return a.second>b.second;
}
ll S_P(){
memset(f,127,sizeof f);
int S=getfa(1);
f[S]=0;
h[0]={S,0};
nh=1;
while (nh){
int x=h[0].first;
ll s=h[0].second;
pop_heap(h,h+nh--,cmph);
if (s>f[x]) continue;
for (EDGE *ei=F.last[x];ei;ei=ei->las)
if (s+ei->w<f[ei->to]){
f[ei->to]=s+ei->w;
h[nh]={ei->to,f[ei->to]};
push_heap(h,h+nh++,cmph);
}
}
int T=getfa(n);
return f[T];
}
int main(){
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);
scanf("%d%d%d",&n,&m,&k);
for (int i=1;i<=m;++i)
scanf("%d%d%d",&ed[i].u,&ed[i].v,&ed[i].w);
sort(ed+1,ed+m+1,cmped);
for (int i=1;i<=n;++i)
fa[i]=i;
for (int i=1;i<=m;++i)
F.link(ed[i].u,ed[i].v,ed[i].w),F.link(ed[i].v,ed[i].u,ed[i].w);
ll ans=S_P();
for (int i=1;i<=m;++i){
int x=getfa(ed[i].u),y=getfa(ed[i].v);
if (x!=y){
fa[x]=y;
F.clear();
for (int j=i+1;j<=m;++j){
x=getfa(ed[j].u),y=getfa(ed[j].v);
int w=ed[j].w-ed[i].w;
if (x!=y)
F.link(x,y,w),F.link(y,x,w);
}
ans=min(ans,(ll)k*ed[i].w+S_P());
}
}
printf("%lld
",ans);
return 0;
}