二分+最短路
求的是一条线路出去k条后的最大值的最小.
这种最值求最值一般都是二分有木有!
所以我们就可以对这个最大值进行二分,如果线路上有大于它的,就需要消耗掉一条免费的,只要最后消耗的小于k就行了。
参考代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e4+10;
const ll mod=1e9+7;
const ll inf=1e18;
ll n,p,k;
ll ans[N];
ll l=inf,r=-inf;
vector<pair<ll,ll> >kano[N];
bool vis[N];
struct Edge {
ll now,step;
Edge(ll a,ll b) {
now=a;
step=b;
}
bool operator < (const Edge a) const {
return step>a.step;
}
};
void Kano(ll x) {
memset(vis,0,sizeof(vis));
for(ll i=1;i<=n;i++)
ans[i]=inf;
ans[1]=0;
priority_queue<Edge>Q;
Q.push(Edge(1,0));
while(!Q.empty()) {
Edge now=Q.top();
Q.pop();
ans[now.now]=min(ans[now.now],now.step);
if(vis[now.now]==0) {
vis[now.now]=1;
for(ll i=0;i<kano[now.now].size();i++) {
ll to=kano[now.now][i].first,val=kano[now.now][i].second;
if(val<x)
Q.push(Edge(to,now.step+0));
else
Q.push(Edge(to,now.step+1));
}
}
}
return ;
}
inline bool check(ll x) {
Kano(x);
if(ans[n]<=k)
return true;
else
return false;
}
int main() {
cin>>n>>p>>k;
for(ll i=1;i<=p;i++) {
ll x,y,z;
cin>>x>>y>>z;
kano[x].push_back(make_pair(y,z));
kano[y].push_back(make_pair(x,z));
l=min(l,z);
r=max(r,z);
}
Kano(r);
if(ans[n]==inf) {
cout<<-1<<endl;
return 0;
}
while(l<=r) {
ll mid=(l+r)/2;
if(check(mid))
r=mid-1;
else
l=mid+1;
}
cout<<l-1<<endl;
return 0;
}
不是应该是 最小的 最大值嘛? 最大值的最小 意思不是 从所有最小的方案中 找出 最大的?
不是,实际上就是让 满足要求的边 的最大值 最小
tql
%%%%