AcWing 847. 图中点的层次
原题链接
简单
作者:
wyzkeyy
,
2023-08-04 23:25:05
,
所有人可见
,
阅读 64
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
int h[N], e[N], ne[N], idx;
int q[N], hh, tt = -1, d[N];
bool st[N];
void add(int a, int b)
{
e[idx] = b;
ne[idx] = h[a];
h[a] = idx ++ ;
}
int main()
{
scanf("%d%d", &n, &m);
memset(h, -1, sizeof(h));
memset(d, -1, sizeof(d));
int a, b;
for (int i = 0; i < m; i ++ )
{
scanf("%d%d", &a, &b);
add(a, b);
}
//bfs宽度搜索直到找到n点
q[ ++ tt] = 1, st[1] = true, d[1] = 0;
int x;
while (hh <= tt)
{
x = q[hh ++ ];
for (int i = h[x]; i != -1; i = ne[i])
{
int j = e[i];
st[x] = true;
if (st[j]) continue;
if (d[j] == -1)
d[j] = d[x] + 1;
if (j == n)
{
printf("%d", d[n]);
return 0;
}
q[ ++ tt] = j;
}
}
printf("%d", d[n]);
return 0;
}