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

import java.io.*;
import java.util.*;

/**
 * @BelongsProject: GXUOJ
 * @Author: Ling xi_Li
 * @CreateTime: 2023-12-04 11-44
 * @Description: TODO 迪杰斯特拉+邻接表
 */

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] nums = in.readLine().split(" ");
        int V = Integer.parseInt(nums[0]);
        int E = Integer.parseInt(nums[1]);

        //邻接表
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        //初始化 5000个点（题目要求）
        for (int i = 0; i < 5000; i++) {
            graph.add(new ArrayList<>());
        }

        //初始化邻接表
        for (int i = 0; i < E; i++) {
            nums = in.readLine().split(" ");
            int begin = Integer.parseInt(nums[0]) - 1;
            int end = Integer.parseInt(nums[1]) - 1;

            graph.get(begin).add(end);
            graph.get(end).add(begin);
        }
        in.close();

        //状态数组
        boolean[] statue = new boolean[5000];
        Arrays.fill(statue, false);
        //路径距离数组
        int[] dist = new int[5000];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[0] = 0;

	  //要实现比较器方法
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.comparingInt(e -> dist[e]));
        queue.add(0);

        while (!queue.isEmpty()) {
            int current = queue.poll();
            //如果已经访问过，跳过
            if (statue[current]) continue;
            statue[current] = true;

            ArrayList<Integer> list = graph.get(current);
            for (int i : list) {
                if (!statue[i] && dist[i] > dist[current] + 1) {
                    dist[i] = dist[current] + 1;
                    queue.add(i);
                }
            }
        }
        if (dist[V - 1] != Integer.MAX_VALUE) out.write(dist[V - 1] + "");
        else out.write("-1");
        out.close();
    }
}