AcWing 847. 图中点的层次
原题链接
简单
作者:
YMYS
,
2024-04-06 00:29:14
,
所有人可见
,
阅读 18
爽!!!!没调试直接过了!!!!!!!
//2024.4.6
//https://www.acwing.com/problem/content/849/
//847.图中点的层次
/*
思路:因为要找最短距离,并且边的权重是1,所以用bfs
*/
#include<bits/stdc++.h> // 包含标准库的头文件
using namespace std; // 使用标准命名空间
const int N = 1e5+10; // 定义全局常量 N
const int M = 2*N;
int n,m;//n点m边
int h[N];//存的几号顶点的idx,只是这里的顶点是头节点
int e[M];//存的是几号顶点的编号idx
int ne[M];//i的下一个邻接点的idx
bool s[N];//判断是否访问过
int idx;//顶点编号
void add(int a,int b){
e[idx] = b;
ne[idx] = h[a];
h[a] = idx;
idx++;
}
int bfs(){
queue<pair<int,int>> p;//first存编号,second存距离
p.push({1,0});
s[1] = true;
while (p.size())
{
auto x = p.front();
p.pop();
int aa = x.first, d = x.second;
if(aa == n) return d;
for(int i = h[aa];i;i=ne[i]){
if(!s[i]) p.push({e[i], d+1});
}
}
return -1;
}
int main() { // 主函数
#ifdef ABC
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\in.in", "r", stdin); // 输入重定向
freopen("D:\\daily_Coding\\VScode-C&C++-Coding\\out.out", "w", stdout); // 输出重定向
#endif
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0); // 关闭流同步,加快输入输出速度
cin>>n>>m;
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs()<<endl;
return 0;
}