首页 > 其他分享 >计蒜客:最短路简化版(BFS)

计蒜客:最短路简化版(BFS)

时间:2024-11-04 20:44:56浏览次数:1  
标签:bfs int 简化版 BFS vector graph push visited 计蒜客

 在queue中用结束标识来节约队列空间。也可以用vector来实现队列,用[left,right]控制队列。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n, m, c;
 4 vector<int> graph[1005];
 5 vector<bool> visited(1005, false);
 6 vector<int> level(1005, 0);
 7 queue<int> q;
 8 void bfs(int l) {
 9     if (q.empty()) {
10         return;
11     }
12     q.push(-1); //加入结束标识
13     while(!q.empty() && q.front() != -1) {
14         int p = q.front();
15         level[p] = l;
16         q.pop();
17         //得到下一批访问节点
18         for (int i : graph[p]) {
19             if (!visited[i]) {
20                 q.push(i);
21                 visited[i] = true;
22             }
23         }
24     }
25     q.pop(); //弹出结束标识-1
26     bfs(l + 1);
27 }
28 int main() {
29     cin >> n >> m >> c;
30     int x, y;
31     while (m --) {
32         cin >> x >> y;
33         graph[x].push_back(y);
34         graph[y].push_back(x);
35     }
36     q.push(c);
37     visited[c] = true;
38     bfs(0);
39     for (int i = 1; i <= n; ++ i) {
40         cout << level[i] << endl;
41     }
42 }

 

标签:bfs,int,简化版,BFS,vector,graph,push,visited,计蒜客
From: https://www.cnblogs.com/coderhrz/p/18526210

相关文章

  • 计蒜客:互粉攻略(DFS/BFS)
     因为有重复数据,所以不得不等输入完以后再进行有向图的遍历。1#include<bits/stdc++.h>2usingnamespacestd;3intn,m;4set<int>graph[1005];5vector<bool>visited(1005,false);6vector<pair<int,int>>degree(1005,make_pair(0,0));//(入度,出度)......
  • 迷宫问题(最短路径)——分别用DFS、BFS解决
    目录问题描述利用DFS(深度优先搜索)求解利用BFS(广度优先搜索)求解问题描述定义一个二维数组N*M,如5 × 5数组下所示:int maze[5][5] = {0, 1, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 0, 0,0, 1, 1, 1, 0,0, 0, 0, 1, 0,};它表示一个迷宫,其中的......
  • BFS和DFS算法全面解析【算法入门】
    1.前言和树的遍历类似,图的遍历也是从图中某点出发,然后按照某种方法对图中所有顶点进行访问,且仅访问一次。但是图的遍历相对树而言要更为复杂。因为图中的任意顶点都可能与其他顶点相邻,所以在图的遍历中必须记录已被访问的顶点,避免重复访问。根据搜索路径的不同,我们可以将遍......
  • BFS + 优先队列
    问题2:走迷宫升级版——边的权值不同单点时限:2.0sec内存限制:256MB一天,sunny不小心进入了一个迷宫,不仅很难寻找出路,而且有的地方还有怪物,但是sunny有足够的能力杀死怪物,但是需要一定的时间,但是sunny想早一点走出迷宫,所以请你帮助他计算出最少的时间走出迷宫,输出这个......
  • 计蒜客:农场看守(DFS、欧拉回路)
     输入样例:451214232434输出样例:12342143241直接对边访问数组进行维护的同时,一次dfs就能走完两遍。没想明白为啥欧拉回路可以这样做。1#include<bits/stdc++.h>2usingnamespacestd;3intn,m;4vector<pair<int,bool>>graph[10005]......
  • ACWing1207_大臣的旅费(bfs)
    有一些自己的理解不知道大家能不能看懂1207.大臣的旅费-AcWing题库高质量的算法题库https://www.acwing.com/problem/content/1209/很久以前,TT 王国空前繁荣。为了更好地管理国家,王国修建了大量的快速路,用于连接首都和王国内的各大城市。为节省经费,TT 国的大臣们经过......
  • 计蒜客:修建大桥(并查集/DFS/BFS)
     找到有几张连通图即可解决问题。DFS:1#include<bits/stdc++.h>2usingnamespacestd;3intn,m;4intgraph[1005][1005]={0};5boolvisited[1005]={false};6voiddfs(intp){7if(visited[p]){8return;9}10visited[p]......
  • BFS(Breath First Search 广度优先搜索)
    @目录一、知识及框架二、案例说明案例1:使用bfs计算二叉树的最小高度案例2:解开密码锁的最少次数,要求:请写一个算法,初始状态为0000,拨出target的最少次数,其中避免出现deadends中的包含的任意一个死亡密码,如果永远无法拨出target,则返回-1本人其他文章链接一、知识及框架BFS算法都是......
  • 计蒜客:公告板(线段树)
     难点在于要把模型抽象出来。第一眼看到题面,想到的是以公告板的高度作为线段树的区间,但看到h<=10^9以后,感觉又开不了这么大的数组。但实际上,最多只有n块公告,所以最极端的情况下不过只有n行,所以区间的真正大小是[1,min(n,h)]。解决了区间的问题,再来考虑每个节点要维护的信息。......
  • 每日OJ题_牛客_AB20走迷宫_BFS_C++_Java
    目录牛客_AB20走迷宫_BFS题目解析C++代码Java代码牛客_AB20走迷宫_BFS走迷宫_牛客题霸_牛客网(nowcoder.com)描述:        给定一个n×m的网格,在网格中每次在不超过边界的情况下可以选择向上、向下、向左、向右移动一格。网格中的一些格子上放置有障碍物,放有......