题目描述
blablabla
样例
#include <iostream>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int h[N], e[N], ne[N], idex;
int n, m, d[N];
void add(int a, int b){
e[idex] = b;
ne[idex] = h[a];
h[a] = idex ++;
}
int bfs(){
queue<int> q;
memset(d, -1, sizeof d);
q.push(1);
d[1] = 0;
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;//求当前节点的d
q.push(j);//队列都是可以走到且第一次走到的节点
}
}
}
return d[n];
}
int main(){
cin >> n >> m;
memset(h, -1, sizeof h);
for(int i = 0; i<m; i++){
int a, b;
cin >> a >> b;
add(a, b);
}
cout << bfs() << endl;
return 0;
}
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla