搜索

2022-11-24 Acwing每日一题


发布时间: 2022-11-24 21:27:00    浏览次数:38 次

本系列所有题目均为Acwing课的内容,发表博客既是为了学习总结,加深自己的印象,同时也是为了以后回过头来看时,不会感叹虚度光阴罢了,因此如果出现错误,欢迎大家能够指出错误,我会认真改正的。同时也希望文章能够让你有所收获,与君共勉!

图中点的层次

给定一个 n 个点 m 条边的有向图,图中可能存在重边和自环。

所有边的长度都是 1,点的编号为 1∼n。

请你求出 1 号点到 n 号点的最短距离,如果从 1 号点无法走到 n 号点,输出 −1。

输入格式
第一行包含两个整数 n 和 m。

接下来 m 行,每行包含两个整数 a 和 b,表示存在一条从 a 走到 b 的长度为 1 的边。

输出格式
输出一个整数,表示 1 号点到 n 号点的最短距离。

数据范围
1≤n,m≤105
输入样例:

4 5
1 2
2 3
3 4
1 3
1 4

输出样例:

1

算法原理

妥妥的广度优先遍历,献上板子来看(这里使用数组模拟队列的方式实现的)。

q[++tt] = x;	// 初始状态入队
while(hh <= tt){
	auto t = q[++hh];	// 取出队头元素
	for(int i=0 ; i<n ; ++i)	// 扩展t的状态
	{
		x = next[t];	// 获得t的下一个状态
		if(!st[x])	//如果这个状态未被遍历过
		{
			q[++tt] = x;	// 将新状态入队
			d[x] += 1;	// 将距离+1
		}
	}
}

看完之后我们再来看这道题,特别裸的一道板子题。明确说了存在重边和自环而且还是寻找最短距离,那么搜索自然需要用BFS广度优先搜索来进行,需要注意的是BFS只能处理无权图,即权重都相等的图,在这里指距离都为1。
需要注意的是这里邻接表h存储的是图的编号,e是存储下一个节点的编号,q队列存储的也是结点编号。

代码实现

#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>

using namespace std;

const int N = 100010;	// 单向图不用加倍

int h[N],e[N],ne[N],idx;	// 存储的是下标
queue<int> q;
int n,m;
int d[N];

void add(int a,int b){
	e[idx] = b,ne[idx] = h[a],h[a] = idx++;
}

int bfs(){
	memset(d,-1,sizeof d);	// 初始化距离哈希
	q.push(1);	// 把编号1放进去,这就是下标
	d[1] = 0;	// 编号1与起点的距离为0
	while(q.size()){
		auto t = q.front();
		q.pop();
		for(int i=h[t]; i != -1 ; i = ne[i]){	// 这个节点能够到那些节点,遍历到这些相邻结点
			int j=e[i];	// 这个编号所对应的编号也就是他的数
			if(d[j] ==  -1){
				d[j] = d[t]+1;	// d[t]表示之前的结点到这个距离+1,就等于这个结点到初始节点的距离d[j]
				q.push(j);	// 将下标入队
			}
		}
	}
	return d[n];	// 1到n的距离为d[n]
}

int main(){
	cin >> n >> m;
	memset(h,-1,sizeof h);
	for(int i=0 ; i<m ; ++i){
		int a,b;
		cin >> a >> b;
		add(a,b);
	}
	cout << bfs() << endl;
	return 0;
}
免责声明 2022-11-24 Acwing每日一题,资源类别:文本, 浏览次数:38 次, 文件大小:-- , 由本站蜘蛛搜索收录2022-11-24 09:27:00。此页面由程序自动采集,只作交流和学习使用,本站不储存任何资源文件,如有侵权内容请联系我们举报删除, 感谢您对本站的支持。 原文链接:https://www.cnblogs.com/WangChe/p/16923505.html