#include <cstring>
#include <iostream>
using namespace std;
const int N=1e5+10;
int h[N], e[N], idx, ne[N];
int d[N]; //存储每个节点离起点的距离 d[1]=0
int n, m; //n个节点m条边
int q[N]; //存储层次遍历序列 0号节点是编号为1的节点
void add(int a, int b)
{
e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}
int bfs()
{
int hh=0,tt=0;
q[0]=1; //0号节点是编号为1的节点
memset(d,-1,sizeof d);
d[1]=0; //存储每个节点离起点的距离
//当我们的队列不为空时
while(hh<=tt)
{
//取出队列头部节点
int t=q[hh++];
//遍历t节点的每一个邻边
for(int i=h[t];i!=-1;i=ne[i])
{
int j=e[i];
//如果j没有被扩展过
if(d[j]==-1)
{
d[j]=d[t]+1; //d[j]存储j节点离起点的距离,并标记为访问过
q[++tt] = j; //把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;
}
关于图的存储和遍历感觉这篇博客讲的很好:https://blog.csdn.net/raelum/article/details/129108365
+1
void add(int x,int y)
{
e[idx]=y; //e存储的是编号
ne[idx]=h[x];//ne存储的是下标为idx的下一个节点的下标
h[x]=idx++;//h存储的是编号为x的的next节点的下标
//可以理解是一个数组,节点一个个存在里面,从0开始存
//idx控制下标一直往右走,而e【idx】存贮的是当前的节点的编号
//ne存的是当前下标里的节点所链接的下一个节点的下标
//h存的则是每个编号节点所对应的数组的位置在哪里,也就是数组的下标
}
这里队尾为什么是0,不是-1 啊
兄弟搞懂了吗
因为已经放进去一个数了,就是起点已经入队了,等同于hh=0,tt=-1,q[++tt]=1
int t=q[hh++];
这个++是什么意思啊取完队头元素,指针向后移动一位
还是想不通为什么要存双倍N
边是点的2n - 1.
#
orz
O∏ZZ
这题自环距离是不是1
只要>=0都不需要考虑了
其实这一题用迪杰斯特拉算法也过了
memset(d,-1,sizeof d);
d[1]=0; //存储每个节点离起点的距离
这两行可以放到main吧?
可以
这题测试样例的正确答案不是2吗,为啥答案是1也能通过呢
1直接到4啊 最短就是1
4和5n和m哈哈哈
很好