算法进阶指南图论 通信线路

通信线路

思路：我们考虑需要升级的那条电缆的花费，若其花费为 w ，那么从 1 到 n 的路径上，至多存在 k 条路径的价值大于 w ，这具有一定的单调性，当花费 w 越大，我们路径上价值大于 w 的花费会越少，由此可以进行二分，求出我们所需要的最小花费。

考虑如何写check 函数，根据上面所说，如果从1-n的路径上，其花费大于 w的数量小于等于 k ，那么即为合法。由此我们可以转化为，对于从1-n路径上的边，若其边权大于 w，则为 1，否则为 0 ，由此就转化为了从1-n的最短路径长度是否小于等于k，运用dijk跑最短路即可，又因为是 0/1边权，所以可以使用双端队列进行优化，整体时间复杂度为 ：$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;
}