家乡网站建设策划案,深圳设计平台,南宁网络推广建站,建工网一级建造师论坛通信线路 思路#xff1a;我们考虑需要升级的那条电缆的花费#xff0c;若其花费为 w #xff0c;那么从 1 到 n 的路径上#xff0c;至多存在 k 条路径的价值大于 w #xff0c;这具有一定的单调性#xff0c;当花费 w 越大#xff0c;我们路径上价值大于 w 的花费会越…通信线路 思路我们考虑需要升级的那条电缆的花费若其花费为 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.husing namespace std;
const int N 1e5 5;
typedef long long ll;
typedef pairll, ll pll;
typedef arrayll, 3 p3;
int mod 1e97;
const int maxv 4e6 5;
// #define endl \nint n,m,k;vectorpll e[N];
int d[N];
bool st[N];
bool check(int x)
{dequeint q;memset(st,0,sizeof st);memset(d,0x3f,sizeof d);d[1]0;q.push_front(1);while(!q.empty()){auto tq.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(w1) q.push_back(u);else q.push_front(u);} }}return d[n]k;
}void solve()
{cinnmk;for(int i1;im;i){int u,v,w;cinuvw;e[u].push_back({v,w});e[v].push_back({u,w});}int l0,r1e65;int ans-1;while(lr){int mid(lr)/2;if(check(mid)){rmid-1;ansmid;}else lmid1;}coutansendl;
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;t1;//cint;while(t--){solve();}system(pause);return 0;
}
