题目链接:https://www.acwing.com/problem/content/description/849/
时/空限制：1s / 64MB

题目描述

给定一个n个点m条边的有向图，图中可能存在重边和自环。

所有边的长度都是1，点的编号为1~n。

请你求出1号点到n号点的最短距离，如果从1号点无法走到n号点，输出-1。

输入格式

第一行包含两个整数n和m。

接下来m行，每行包含两个整数a和b，表示存在一条从a走到b的长度为1的边。

输出格式

输出一个整数，表示1号点到n号点的最短距离。

数据范围

1≤n,m≤10^5

输入样例

4 5
1 2
2 3
3 4
1 3
1 4

输出样例

1

解题思路

题意:给你n个点和m条边，求1~n的最短距离。
思路:直接从1开始BFS就行了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = MAXN << 1;
const int inf = 0x3f3f3f3f;
struct edge {
    int u, t;
    edge() {}
    edge(int u, int t) : u(u), t(t) {}
};
struct AdjTab {
    int u, v;
    AdjTab() {}
    AdjTab(int u, int v) : u(u), v(v) {}
}e[MAXN];
bool vis[MAXN];
int f[MAXN], Adj = 0;
void Add_Adj(int u, int v) {
    e[++Adj] = AdjTab(f[u], v);
    f[u] = Adj;
}
int BFS(int s, int t) {
    queue <edge> Q;
    Q.push(edge(s, 0));
    vis[s] = true;
    while (!Q.empty()) {
        edge p = Q.front();
        Q.pop();
        if (!(p.u != t))
            return p.t;
        for (int i = f[p.u]; ~i; i = e[i].u) {
            int v = e[i].v;
            if (!vis[v]) {
                vis[v] = true;
                Q.push(edge(v, p.t + 1));
            }
        }
    }
    return -1;
}
int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    memset(f, -1, sizeof(f));
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        Add_Adj(u, v);
    }
    printf("%d\n", BFS(1, n));
    return 0;
}