关于bfs：
你怎么会连这个都不知道！！！自己好好谷歌一下！！！（其实我也刚学）
bfs伪代码：
1
2
3
4
5
6
7
8
9
10
|
while(队列非空){
取出队首元素u;
弹出队首元素;
u染色为黑色;
for(int i=0;i<u的出度){
if(i非白色) continue;
u的第i个出线连着的点入队;
i染为灰色;
}
}
|
可爱的分割线
无权最短路
显然，你在洛谷上是搜不到这题的，因为这是我们学校团队的题。所以还是找个小板凳专心听我讲吧。
题目描述：
给定无权无向图G(V,E)和源点s/终点t，求 s->t 的最短路径。
假设读入边的列表是有（字典）序的（既邻接表就是有序的）。
输入输出格式：
输入格式：
第一行包含4个整数N、M、s、t，表示该图共有N个结点和M条无向边。（N <= 5000，M <= 200000）。起点为s，终点为t。
接下来M行，每行包含2个整数{u,v}，表示有一条无向边连接结点u、v
输出格式：
输出最短路的长度（边数）
若无法到达，输出"No path"
样例：
输入：
1
2
3
4
|
4 3 1 4
1 2
1 3
2 4
|
输出：
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
|
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
const int NR=5005;
using namespace std;
struct Edge{
//一个存储权值的结构体，为bfs模板，此题无用
int v,w;
Edge(int v,int w):v(v),w(w){}
};
vector<Edge> save[5005];//邻接表
int d[NR];//记录距离的数组
int main()
{
int n,m,s,t;
cin>>n>>m>>s>>t;//输入
char color[n+1];//判断是否去过（没去过:"w"，正在考虑（在队列中）:"g"，已经完全考虑:"b"）
memset(color,'w',sizeof(color));//染色数组重置为白色
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;//输入每条线的起点和终点
save[a].push_back(Edge(b,1));//因为是无向图，所以在起点连接的点中增加终点
save[b].push_back(Edge(a,1));//还要在终点连接的点中增加起点
}
d[s]=0;//起点距离起点的距离设为零
queue<int> q;//bfs处理队列
q.push(s);//起点入队
color[s]='g';//起点染色成灰色
while(!q.empty()){
int u=q.front();//取出队首的一项
q.pop();//弹出
color[u]='b';//标记为黑色
for(int i=0;i<save[u].size();i++){//拓展出所有子节点
if(color[save[u][i].v]!='w') continue;
if(save[u][i].v==t){
cout<<d[u]+1;//如果这个位置是终点，则输出
return 0;
}
d[save[u][i].v]=d[u]+1;//计算距离
color[save[u][i].v]='g';//染灰色
q.push(save[u][i].v);//进队
}
}
cout<<"No path";
return 0;
}
|