题目描述
能力不够不能精简的概括…
在郊区有 N 座通信基站,P 条 双向 电缆,第 i 条电缆连接基站Ai和Bi。
特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。
现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费Li。
电话公司正在举行优惠活动。
农产主可以指定一条从 1 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。
求至少用多少钱可以完成升级。
样例
5 7 1
1 2 5
3 1 4
2 4 8
3 2 3
5 2 9
3 4 7
4 5 6
4
分析
1.在最大求最小,最小求最大首先考虑二分答案
2.确定我们不升级的边的长度过后,就要确定有没有这样一种情况存在能使我们到n的路上,超过我们设定的长度的边的数量有没有超过k就行了。
3.这里因为既要入头又要入尾,可以数组模拟队列也可以直接用库函数
C++ 代码
#include<bits/stdc++.h>//一堆乱塞的必要文件
#define ll long long
using namespace std;
const int N=1e3+7,M=1e5+7;//一堆莫名其妙的定义
ll n,q,k,t,net[N];
struct mn{
ll to,nex,d;
}s[M<<1];
void add(int a,int b,int c){//邻接表建图
s[++t].d=c;
s[t].to=b;
s[t].nex=net[a];
net[a]=t;
}
int w[M],head,tail;//模拟队列使用时的定义
ll dis[N];
bool h[N];
void init(){// 每次判断时的初始化内容
memset(dis,0x3f,sizeof(dis));
memset(h,0,sizeof(h));
dis[1]=0;
w[5000]=1;//防止出锅
head=5000;tail=5000;
}
bool check(int xz){//对答案是否可行的判断
init();
while(head<=tail){
int t=w[head++];
if(h[t])
continue;
h[t]=1;
for(int i=net[t];i;i=s[i].nex){
int c=s[i].to,key=s[i].d>xz;
if(dis[c]>dis[t]+key)
dis[c]=dis[t]+key;
if(!key)
w[--head]=c;
else w[++tail]=c;
}
}
return dis[n]<=k;
}
int main()//输入+二分答案+输出答案
{
scanf("%lld %lld %lld",&n,&q,&k);
int a,b,c;
for(int i=1;i<=q;i++){
scanf("%d %d %d",&a,&b,&c);
add(a,b,c);
add(b,a,c);
}
ll l=0,r=1e6+1;
while(l<r){
ll mid=(l+r)>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
if(r==1e6+1)
r=-1;
cout<<r;
return 0;
}