通信线路
思路:我们考虑需要升级的那条电缆的花费,若其花费为 w ,那么从 1 到 n 的路径上,至多存在 k 条路径的价值大于 w ,这具有一定的单调性,当花费 w 越大,我们路径上价值大于 w 的花费会越少,由此可以进行二分,求出我们所需要的最小花费。
考虑如何写check 函数,根据上面所说,如果从1-n的路径上,其花费大于 w的数量小于等于 k ,那么即为合法。由此我们可以转化为,对于从1-n路径上的边,若其边权大于 w,则为 1,否则为 0 ,由此就转化为了从1-n的最短路径长度是否小于等于k,运用dijk跑最短路即可,又因为是 0/1边权,所以可以使用双端队列进行优化,整体时间复杂度为 : n l o g n nlogn nlogn
#include <bits/stdc++.h>using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"int n,m,k;vector<pll> e[N];
int d[N];
bool st[N];
bool check(int x)
{deque<int> q;memset(st,0,sizeof st);memset(d,0x3f,sizeof d);d[1]=0;q.push_front(1);while(!q.empty()){auto t=q.front();q.pop_front();if(st[t]) continue;st[t]=1;for(auto [u,w]: e[t]){w = w> x? 1: 0;if(d[u]>d[t]+w){d[u]=d[t]+w;if(w==1) q.push_back(u);else q.push_front(u);} }}return d[n]<=k;
}void solve()
{cin>>n>>m>>k;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;e[u].push_back({v,w});e[v].push_back({u,w});}int l=0,r=1e6+5;int ans=-1;while(l<=r){int mid=(l+r)/2;if(check(mid)){r=mid-1;ans=mid;}else l=mid+1;}cout<<ans<<endl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t=1;//cin>>t;while(t--){solve();}system("pause");return 0;
}