https://www.acwing.com/problem/content/849/
本题为经典的图形插入遍历题目
首先是手写链表 实现
#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];// 保存1号点到各个点的距离 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(); // 循环遍历所有与t相距为1的节点 for (int i = h[t]; i != -1; i = ne[i]) // ne[i]上的点都是与i节点距离为1的点 { int j = e[i]; // 向外走一步 if (d[j] == -1) // 如果j没有被遍历过 { d[j] = d[t] + 1; // 因为路径长度都是1,所以直接在上一步的基础上加上1即可 q.push(j); // 将j加到队列中 } } } return d[n]; // 返回的d[n]即是节点1到节点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; }
但本人还是喜欢用stl,虽然慢,vector
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int n, m; vector<int> h[N]; int d[N]; int bfs() { memset(d, -1, sizeof d); queue<int> q; q.push(1); d[1] = 0; while (q.size()) { int t = q.front(); q.pop(); for (auto i: h[t]) { if (d[i] == -1) { d[i] = d[t] + 1; q.push(i); } } } return d[n]; } int main() { scanf ("%d%d", &n, &m); for (int i = 0; i < m; i ++ ) { int a, b; scanf ("%d%d", &a, &b); h[a].push_back(b); } cout << bfs() << endl; return 0; }