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

import java.util.*;
public class Main {
    public static boolean[] visited = new boolean[5001];
    public static HashMap<Integer, ArrayList<Integer>> edges= new HashMap<>();
    public static int[] length = new int[5001];
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int target = input.nextInt();
        int edgeNum = input.nextInt();
        int ver1;
        int ver2;
        Arrays.fill(length,50001);

        for(int i = 0; i < edgeNum; i++){
            ver1 = input.nextInt();
            ver2 = input.nextInt();
            update(ver1,ver2);
            update(ver2,ver1);
        }
        length[1] = 0;
        setLength(target);

    }
    public static void update(int ver1, int ver2){
        if(edges.containsKey(ver1)){
            edges.get(ver1).add(ver2);
        }else{
            ArrayList<Integer> list = new ArrayList<>();
            list.add(ver2);
            edges.put(ver1,list);
        }
    }
    public static void setLength(int target){
        int start;
        int index = 0;
        while(index < 5000){
            start = getStart();
            if(start == -1){
                break;
            }
            if(start == target){
                System.out.println(length[target]);
                return;
            }else{
                updateLength(start);
            }
            index++;
        }
        System.out.println(-1);
    }
    public static int getStart(){
        int start = -1;
        int min = 50001;
        for(int i = 1; i < 5001; i++){
            if(!visited[i] && length[i] < min){
                min = length[i];
                start = i;
            }
        }
        if(start!=-1){
            visited[start] = true;
        }
        return start;
    }
    public static void updateLength(int start){
        for(int i = 1; i < 5001; i++){
            if(!visited[i] && edges.get(start).contains(i)){
                if(length[i] > length[start] + 1){
                    length[i] = length[start]+1;
                }
            }
        }
    }
}