数组模拟队列

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
int n, m;
int h[N], e[N], ne[N], idx; // 使用邻接表存储图
int D[N], Q[N]; // 存储距离和队列(使用数组模拟队列)

// 头插法插入边(x-y)
void ins(int x, int y){
    e[idx]=y;
    ne[idx]=h[x];
    h[x]=idx++;
}


int bfs(){
    int HEAD=0;
    int TAIL=0;
    Q[HEAD]=1;
    D[1]=0;
    while(HEAD<=TAIL){
        int source=Q[HEAD++]; // 起点s出队
        for(int i=h[source]; i!=-1; i=ne[i]){ // 在邻接表中遍历s的所有邻接节点
            int dest = e[i];
            if(D[dest]==-1){
                D[j]=D[dest]+1; // 更新source-dest的距离
                Q[++TAIL]=j; // 邻接节点插入队列
            }
        }
    }
    return D[n];
}


int main(){
    cin>>n>>m;
    memset(h, -1, sizeof h);
    memset(D, -1, sizeof D);
    int x, y;
    while(m--){
        cin>>x>>y;
        ins(x, y);
    }

    cout<<bfs()<<endl;

    return 0;
}

调用容器(vector存储有向图)

#include <bits/stdc++.h>
using namespace std;

const int N=1e5+5;
vector<int> G[N];
int dis[N];
int n, m;

int bfs(int source){
    queue<int> q;
    q.push(source);
    dis[source]=0;
    while(!q.empty()){
        int node = q.front();
        q.pop();
        for(auto &e: G[node]){
            if(dis[e]==-1){
                dis[e]=dis[node]+1;
                q.push(e);
            }
        }
    }

    return dis[n];
}


int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    memset(dis, -1, sizeof dis);
    cin>>n>>m;
    for(int i=0; i<n; ++i) G[i].clear();
    int x, y;
    while(m--){
        cin>>x>>y;
        G[x].push_back(y);
    }
    cout<<bfs(1)<<endl;

    return 0;
}