AcWing 847. java详细注释
原题链接
简单
作者:
季之秋
,
2021-01-17 21:45:48
,
所有人可见
,
阅读 305
import java.util.*;
public class Main{
static int[] e,ne,h,g,d;
static int n,m,idx,N=100010;
static class Pair{//初始化数组
Pair(){
e=new int[N];//链表值
ne=new int[N];//指向的下一个
g=new int[N];//地图
h=new int[N];//链表头数组
d=new int[N];//到某一点的距离
Arrays.fill(h,-1);//-1代表空
Arrays.fill(d,-1);
}
void add(int a,int b){//以a为头的链表后面插入b值;下标指针为idx
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
Pair q=new Pair();
for(int i=0;i<m;i++){//插入m个关系后
int a=sc.nextInt();
int b=sc.nextInt();
q.add(a,b);
}
System.out.println(bfs());
}
static int bfs(){
int tt=0,hh=0;//头和尾
g[0]=1;//有一个初始值,所以tt从1开始插入值
d[1]=0;//本身的距离0
while(hh<=tt){//队列里面有值
int t=g[hh++];//取对头
for(int i=h[t];i!=-1;i=ne[i]){//遍历队头可以走的所有值
int j=e[i];//j保存遍历到的值
if(d[j]==-1){//没被访问过的话
g[++tt]=j;//加入队列
d[j]=d[t]+1;//这个点在之前的距离上就加一(保存距离)
}
}
}
return d[n];
}
}