邻接表 加 模拟队列
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N=1e5+10;
const int M=2*N;
int h[N],e[M],ne[M],idx;
int d[N];
int q[N]; // 模拟队列
int n,m;
void Init(){
memset(h,-1,sizeof h);
memset(d,-1,sizeof d);
}
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(){
int hh=0,tt=0;
q[0]=1;
d[1]=0;
while(hh<=tt){
int u=q[hh++]; // 取出 对头
for(int i=h[u];i!=-1;i=ne[i]){
int j=e[i];
if(j==n) return d[u]+1;
if(d[j]==-1) { //没有被搜过
d[j]=d[u]+1;
q[++tt]=j;
}
}
}
return -1;
}
int main(){
Init();
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs()<<endl;
return 0;
}
邻接表 加 stl队列
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N=1e5+10;
const int M=2*N;
int h[N],e[M],ne[M],idx;
bool st[N];
int n,m;
struct node{
int id;
int cnt;
};
void Init(){
memset(h,-1,sizeof h);
}
void add(int a,int b){
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs(){
queue<node>q;
node p;
p.id=1,p.cnt=0;
q.push(p);
st[1]=true;
while(q.size()){
node p1=q.front();
for(int i=h[p1.id];i!=-1;i=ne[i]){
int j=e[i];
if(j==n) return p1.cnt+1;
if(!st[j]) {
st[j]=true;
node pp;
pp.cnt=p1.cnt+1;
pp.id=j;
q.push(pp);
}
}
q.pop();
}
return -1;
}
int main(){
Init();
cin>>n>>m;
while(m--){
int a,b;
cin>>a>>b;
add(a,b);
}
cout<<bfs()<<endl;
return 0;
}