因为这道题的边长为1，所以可以用宽搜
1 #include <bits/stdc++.h> 2 using namespace std; 3 const int N = 100010; 4 int h[N], e[N], ne[N], idx; 5 int d[N]; 6 int n, m; 7 void add(int a, int b) { 8 e[idx] = b; 9 ne[idx] = h[a]; 10 h[a] = idx; 11 idx++; 12 } 13 int bfs() { 14 memset(d, -1, sizeof(d)); //表示都没有遍历过 15 queue<int> q; 16 q.push(1); 17 d[1] = 0; 18 while (q.size()) { 19 int t = q.front(); 20 q.pop(); 21 for (int i = h[t]; i != -1; i = ne[i]) { 22 int j = e[i]; 23 if (d[j] == -1) { 24 d[j] = d[t] + 1; 25 q.push(j); 26 } 27 } 28 } 29 return d[n]; 30 } 31 int main() { 32 memset(h, -1, sizeof(h)); 33 cin >> n >> m; 34 while (m--) { 35 int a, b; 36 cin >> a >> b; 37 add(a, b); 38 } 39 cout << bfs() << endl; 40 return 0; 41 }