当前位置:网站首页>AcWing 340. Solution to communication line problem (binary + double ended queue BFS for the shortest circuit)
AcWing 340. Solution to communication line problem (binary + double ended queue BFS for the shortest circuit)
2022-07-02 19:43:00 【Mr. Qiao Da】
AcWing 340. Communication lines
y Always say yes noip Improve the level of the Group , It's really difficult to change the meaning of the question , It's hard to find a solution , I hope I can write this level of questions by myself one day
Their thinking : Two points + deque BFS Find the shortest path , It is difficult to change thinking , Several turning points of thinking are :① Find a suitable less than k Value x, Two points .② In judging x When appropriate , You can use a double ended queue to find the shortest path
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3 + 10, M = 2e4 + 10, INF = 0x3f3f3f3f;
int h[N], ne[M], e[M], w[M], idx;
bool st[N];
deque<int>q;
int n, m, p, k;
int dist[N];
void add(int a, int b, int c){
e[idx] = b;
w[idx] = c;
ne[idx] = h[a];
h[a] = idx ++ ;
}
bool check(int bound){
// The weight of the opposite side is only 0/1 The graph uses a double ended queue to search widely to find the shortest path
memset(st, 0, sizeof st);
memset(dist, 0x3f, sizeof dist);
dist[1] = 0;
q.push_front(1);
while(q.size()){
int op = q.front();
q.pop_front();
if(st[op]) continue;
st[op] = true;
for(int i = h[op]; ~i; i = ne[i]){
int j = e[i], v = w[i] > bound;
if(dist[j] > dist[op] + v){
dist[j] = dist[op] + v;
if(!v) q.push_front(j);
else q.push_back(j);
}
}
}
return dist[n] <= k; // The edge weight in the return graph is greater than bound Whether the number of edges of is greater than k
}
int main()
{
cin>>n>>m>>k;
memset(h, -1, sizeof h);
while(m -- ){
int a, b, c;
cin>>a>>b>>c;
add(a, b, c);
add(b, a, c);
}
// Two points to find the right value mid
// The right value mid It means having mid The weight of the edge is assigned 0 when , The shortest path can be found
// Here I have always wondered why the dichotomy mid It must be the weight in the graph
// After reading the detailed explanation of other bosses, I understand
//① The first understanding , If mid It is not the weight existing in the graph , So this time check The result is the same as last check The results returned are the same , Two points won't stop
//② The second understanding , The essence of dichotomy is to find the minimum , If mid Not the edge weights that exist in the graph , Then there must be a smaller number of edge weights , Chapter II continued , Until the smallest qualified value is found
// In a word , Two points is the best value , Instead of being appropriate
int l = 0, r = 1e6 + 1;
while(l < r){
int mid = l + r >> 1;
if(check(mid)) r = mid;
else l = mid + 1;
}
if(r == 1e6 + 1) r = -1;
cout<<r<<endl;
return 0;
}
边栏推荐
- rxjs Observable 自定义 Operator 的开发技巧
- Chapter 7 - class foundation
- AcWing 1129. 热浪 题解(最短路—spfa)
- pxe装机「建议收藏」
- KT148A语音芯片ic的开发常见问题以及描述
- Implementation of 453 ATOI function
- 《重构:改善既有代码的设计》读书笔记(下)
- Implementation of 452 strcpy, strcat, StrCmp, strstr, strchr
- Infix expression is converted to suffix expression (C language code + detailed explanation)
- 多态的理解以及作用
猜你喜欢
SQLite 3.39.0 发布,支持右外连接和全外连接
Educational codeforces round 129 (rated for Div. 2) supplementary problem solution
zabbix5客户端安装和配置
Build a master-slave mode cluster redis
冒泡排序数组
Refactoring: improving the design of existing code (Part 1)
450-深信服面经1
KT148A语音芯片使用说明、硬件、以及协议、以及常见问题,和参考代码
Detailed tutorial on installing stand-alone redis
Shardingsphere jdbc5.1.2 about select last_ INSERT_ ID () I found that there was still a routing problem
随机推荐
Reading notes of "the way to clean structure" (Part 2)
MySQL表历史数据清理总结
451 implementation of memcpy, memmove and memset
Automatically generate VGg image annotation file
R language uses econcharts package to create microeconomic or macroeconomic maps, and indifference function to visualize indifference curve
Notes on hardware design of kt148a voice chip IC
KT148A语音芯片ic的软件参考代码C语言,一线串口
pxe装机「建议收藏」
451-memcpy、memmove、memset的实现
Development skills of rxjs observable custom operator
Dictionaries
编写完10万行代码,我发了篇长文吐槽Rust
《架构整洁之道》读书笔记(下)
《MongoDB入门教程》第03篇 MongoDB基本概念
Is there any security guarantee for the ranking of stock and securities companies
Chapter 7 - class foundation
搭建主从模式集群redis
mysql函数
Génération automatique de fichiers d'annotation d'images vgg
Windows2008r2 installing php7.4.30 requires localsystem to start the application pool, otherwise 500 error fastcgi process exits unexpectedly