AcWing 847. 图中点的层次

3 days before CCC Stage 1

一道常规的有向无权图，可以直接用BFS寻找最短距离

这里其实还可以手动实现队列，不过STL内置的队列就足够所有用途了，所以没必要

重要的是理解BFS的思路是用队列实现的，然后能快速熟练用数组模拟出邻接表

而且这里用不到bool st[N];，因为初始化距离为-1，如果不是-1即为访问过此点，所以可以少写好几行xD

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 100010;

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

void add(int a, int b){
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

int bfs(){
    memset(d, -1, sizeof d);

    queue<int> q;
    d[1] = 0;
    q.push(1);

    while(q.size()){
        int t = q.front();
        q.pop();

        for(int i = h[t]; i != -1; i = ne[i]){
            int j = e[i];
            if(d[j] == -1){
                d[j] = d[t] + 1;
                q.push(j);
            }
        }
    }

    return d[n];
}

int main(){
    scanf("%d%d", &n, &m);
    memset(h, -1, sizeof h);

    for(int i = 0; i < m; i++){
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
    }

    cout << bfs() << endl;

    return 0;
}