图中点的层次

一、题目

宽搜模板题：https://www.acwing.com/problem/content/849/

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

所有边的长度都是 $1$ ，点的编号为 $1 \sim n$ 。

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

输入格式

第一行包含两个整数 $n$ 和 $m$ 。

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

输出格式

输出一个整数，表示 $1$ 号点到 $n$ 号点的最短距离。

数据范围

$1 \le n,m \le 10^5$

输入样例：

输出样例：

二、题解

1. `memset()` 初始化

在对数组进行初始化时，可能会用到 memset()，其初始化特点是按字节去逐个初始化，可以将数组初始化为 $-1$ 、 $0$ 、 $0x3f$ 。其中，使用 $-1$ 、 $0$ 、 $0x3f$ 初始化时，分别能够将数组初始化为 $-1$ 、 $0$ 、无穷大。（如果要初始化为其他值，则使用 for循环 较好。）

比如，把数组初始化为 100，如果使用 memset() 进行初始化：
因为 100 的二进制表示为 01100100，那么使用 memset() 初始化后，该数组中每一项的二进制表示为 01100100 01100100 01100100 01100100，转换成十进制为 1684300900，而不是 100。

为什么使用0x3f3f3f3f定义无穷大呢？

因为0x3f3f3f3f转换成十进制为1061109567，是10^9级别的，其足够大；其次，也是最重要的，0x3f3f3f3f + 0x3f3f3f3f等于0x7e7e7e7e，不会爆int。

在很多算法中，我们需要进行诸如dist[j] > dist[t] + w[t][j]之类的判断，如果两个大于0x3f3f3f3f的数相加，那么后果不堪设想。因为溢出并不会报错，算法逻辑复杂，我们往往很难定位真正的错误。

参考链接: https://blog.csdn.net/2301_79599253/article/details/135737272 、https://cloud.tencent.com/developer/article/1877662

2. 图的存储：邻接表

使用邻接表存储图，其中：
用h[]保存各个节点能到的第一个节点的编号，开始时，h[]全部为-1；用e[]保存节点编号，ne[]保存e[]对应位置的下一个节点所在的索引；用idx保存下一个e[]中，可以放入节点位置的索引。

插入边使用的头插法，例如插入：a->b。首先把b节点存入e数组，e[idx] = b；然后b节点的后继是h[a]，ne[idx] = h[a]；最后，a的后继更新为b节点的编号，h[a] = idx，索引指向下一个可以存储节点的位置，idx ++。

void add(int a, int b)      // 在邻接表中添加 a->b 的有向边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

3. 邻接表的BFS遍历

从h[fro]指向的头节点开始遍历，以i = ne[i]更新变量i，以i != -1为结束条件，遍历以fro节点为起点的有向边，分别更新距离、队列和是否被访问。

for (int i = h[fro]; i != -1; i = ne[i] )   // 遍历和fro节点存在有向边的节点 fro->
{
	int las = e[i];     // 后节点
	if (!st[las])
	{
		dist[las] = dist[fro] + 1;      // 更新距离
		q.push(las);        // 更新队列
		st[las] = true;     // 更新是否被访问
	}
}

4. 如何求出距离？如何避免重环和自环？

对于题目中的距离的求解，可以根据当前遍历层距离计算下一层距离。初始状态下，所有距离的初值为0x3f3f3f3f，从第一个节点开始遍历，故第一个节点的距离为0。比如，当前遍历的节点为fro，且通过计算已经得出到达其的最短距离，则其下一个节点的距离为dist[fro] + 1。

为了避免重环和自环，可以通过一个标志位（该节点是否被访问过），使每个节点只遍历一次。在更新距离的过程中，不断更新此标志位。

5. `queue` 相关

#include <quque>	// 头文件
queue<int> q;		// 创建一个名为q，存储int型数据的队列
q.size();			// 返回当前队列的大小
int a = 10;
q.push(a);			// 队尾添加一个元素
q.front();			// 返回队首元素
q.pop();			// 弹出队首元素
q.empty();			// 如果队列为空 返回true

三、代码

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

using namespace std;

const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;     // 邻接表数据结构
int dist[N];    // dist存储距离
bool st[N];     // st标记是否走到过

void add(int a, int b)      // 在邻接表中添加 a->b 的有向边
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()  // 宽搜
{
    memset(dist, 0x3f, sizeof dist);    // 初始化距离为无穷大
    dist[1] = 0;    // 从1开始，到1的距离为0
    queue<int> q;
    q.push(1), st[1] = true;    // 已经访问第一个节点，放入队列，且标记为访问
    while (q.size())    // 如果队列非空
    {
        int fro = q.front();    // 提取队首元素
        q.pop();
        for (int i = h[fro]; i != -1; i = ne[i] )   // 遍历和fro节点存在有向边的节点 fro->
        {
            int las = e[i];     // 后节点
            if (!st[las])
            {
                dist[las] = dist[fro] + 1;      // 更新距离
                q.push(las);        // 更新队列
                st[las] = true;     // 更新是否被访问
            }
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);    // 初始化邻接矩阵的索引
    cin >> n >> m;
    for (int i = 0; i < m; i ++ )
    {
        int a, b;
        cin >> a >> b;
        add(a, b);      // 添加有向边
    }
    bfs();
    cout << (dist[n] == 0x3f3f3f3f ? -1 : dist[n]) << endl;     // 输出距离
    return 0;
}