二分+dij题目
首先读一遍题目，一定要仔细读（不要问我为什么，我就是受害者qwq
你会发现最终的费用是由最长的电话线决定的，而非电话线长度和。
至此就有了一个基本思路——枚举（二分）出可能的最长电话线长度，然后对其进行dij判断。
dij思路如下：
1.已知枚举出了假定答案ans；
2.在最短路过程中，判断有多少条线长度大于ans，并将其免费；
3.最后判断免费条数，若大于给出的t即不可行，反之可行。
开long long！！！
代码：
#include<bits/stdc++.h>
using namespace std;
long long ca,k,ma,ans,cnt,n,m,vis[2050],a,b,dis[2050],nex[20500],fst[2050],v[20500],w[20500],f[2050],sum[2050],ww;
int dj(long long ans)
{
memset(dis,0x7f/3,sizeof(dis));
memset(vis,0,sizeof(vis));
dis[1]=0;
long long minn,t=0;
for(register long long i=1;i<=n;i++)
{
minn=1e12;
for(long long j=1;j<=n;j++)
{
if(!vis[j]&&dis[j]<minn)
{
minn=dis[j];
t=j;
}
}
vis[t]=1;
for(register long long j=fst[t];j;j=nex[j])
{
if(w[j]>ans)
dis[v[j]]=min(dis[v[j]],dis[t]+1);
else
dis[v[j]]=min(dis[v[j]],dis[t]);
}
}
if(dis[n]>1e8)
{
cout<<-1;
return 2;
}
if(dis[n]>k)
return 0;
return 1;
}
void binary(long long l,long long r)
{
if(l>r)
{
cout<<ans;
return ;
}
long long mid=(l+r)>>1;
int dij=dj(mid);
if(dij==2)
return;
if(dij==1)
{
ans=mid;
binary(l,mid-1);
}
else
binary(mid+1,r);
return ;
}
int main()
{
scanf("%lld%lld%lld",&n,&m,&k);
for(long long i=1;i<=m;i++)
{
scanf("%lld%lld%lld",&a,&b,&ww);
ma+=ww;
nex[++cnt]=fst[a];
fst[a]=cnt;
v[cnt]=b;
w[cnt]=ww;
nex[++cnt]=fst[b];
fst[b]=cnt;
v[cnt]=a;
w[cnt]=ww;
}
binary(0,ma);
return 0;
}