题解 | #【模板】单源最短路1#

总结：
1.java中boolean默认为flase,对象默认为null
2.无权图计算单源最短路径可以使用广度优先算法，借助队列记忆将要访问的下一层顶点。可以使用visited[]标志顶点是否被访问过，以防止被多次访问。

import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String[] line = sc.nextLine().split(" ");
        int n = Integer.parseInt(line[0]);
        int edgesNum = Integer.parseInt(line[1]);
        int[][] arr = new int[5001][5001];
        for(int i=0;i<edgesNum;i++){
            line = sc.nextLine().split(" ");
            arr[Integer.parseInt(line[0])][Integer.parseInt(line[1])] = 1;
            arr[Integer.parseInt(line[1])][Integer.parseInt(line[0])] = 1;
        }
        System.out.println(shortestPath(arr,n));
    }
    public static int shortestPath(int[][] arr,int n){
        boolean[] visited = new boolean[5001];//java中boolean默认为flase,对象默认为null
        Queue<int[]> queue = new LinkedList<>();
        for(int j=1;j<arr[1].length;j++){
            if(arr[1][j]==1){
                queue.add(new int[]{j,1});
                visited[j] = true;
                if(j == n)
                    return 1;
            }
        }
        int len = arr.length;
        while(!queue.isEmpty()){
             int[] e = queue.poll();
            for(int k = 1;k<arr[e[0]].length;k++){
                if(arr[e[0]][k]==1){
                    if(!visited[k]){
                        queue.add(new int[]{k,e[1]+1});
                        visited[k] = true;
                        if(k == n)
                            return e[1]+1;
                    }
                }
            }
        }
        return -1;

        }

}