图中点的层次（树与图的广度优先遍历）

原题链接https://www.acwing.com/problem/content/849/

给定一个 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

题意理解：
关于重边与自环：

就是最短路问题，所以采用广度搜索，因为广度搜索每个被搜到的一定是离他最近的距离；
使用的数据结构：队列；
一般框架:
1.队列需要初始化，hh,tt，还有入队，距离要变为-1,之后也用它来表示未访问到；

int hh=0,tt=-1;
q[++tt]=1;//入队的编号
memset(d,-1,sizeof d);//距离置为1
d[1]=0;//初始化第一个

2.用一个while当队列不空时，取出队头并出队，然后以取出的元素进行拓展；
然后拓展中会有一系列的判断，如果满足条件之后，那么距离+1，并且入队；

while(hh<=tt)
{
	int t=q[hh++];
	for(int i=h[t];i!=-1;i=ne[i])
	{
		int j=e[i];
		if(d[j]==-1)
		{
			d[j]=d[t]+1;
			q[++tt]=j;
		}
	}
}

实现：

#include
#include

using namespace std;

const int N=1e5+100;

int h[N],e[N],ne[N],idx;
int d[N];
int q[N];
int n,m;

void add(int a,int b)
{
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
    int hh=0,tt=-1;
    q[++tt]=1;
    memset(d,-1,sizeof d);
    d[1]=0;
    while(hh<=tt)
    {
        int t=q[hh++];
        for(int i=h[t];i!=-1;i=ne[i])
        {
            int j=e[i];
            if(d[j]==-1)
            {
                d[j]=d[t]+1;
                q[++tt]=j;
            }
        }
    }
    return d[n];
}
int main()
{
    memset(h,-1,sizeof h);
    cin>>n>>m;
    for(int j=0;j
        int a,b;
        cin>>a>>b;
        add(a,b);
    }
    printf("%dn",bfs());
    return 0;
}

总结：
1，邻接表的存储不断熟练，凡是涉及到图的都会使用；
2，广度优先遍历总体框架有一定印象，多加练习；