/* 4 5 1 2 2 3 3 4 1 3 1 4 */ //此样例输出结果为1 #include<iostream> #include<queue> #include<cstring> using namespace std; const int N=10010; int he[N],e[N],ne[N],idx=0; //链表存树 int d[N],n,m; void add(int a,int b) //类似链表操作 { e[idx]=b; //注意e[]存节点序号 下面判断要用 ne[idx]=he[a]; he[a]=idx++; } int bfs() { //典型bfs模板 没啥好说的 d[1]=0; queue<int>que; que.push(1); while(!que.empty()) { int t=que.front(); que.pop(); for(int i=he[t];i!=-1;i=ne[i]) { if(d[e[i]]==-1) { d[e[i]]=d[t]+1; que.push(e[i]); } } } return d[n]; } int main(void) { cin>>n>>m; memset(d,-1,sizeof(d)); //d数组存每个点到起点的距离 memset(he,-1,sizeof(he)); //初始化链表 for(int i=0;i<m;i++) { int a,b; cin>>a>>b; add(a,b); } cout<<bfs()<<endl; return 0; }
0.0分
1 人评分
C语言程序设计教程(第三版)课后习题6.7 (C语言代码)浏览:647 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:751 |
A+B for Input-Output Practice (II) (C语言代码)浏览:1002 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:687 |
wu-淘淘的名单 (C++代码)浏览:1339 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:648 |
三角形 (C语言代码)浏览:914 |
Hello, world! (C++代码)浏览:1745 |
DNA (C语言描述,蓝桥杯)浏览:1555 |
Cylinder (C语言描述,蓝桥杯)浏览:1247 |