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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static class Enter {
         int id;
         int weight;
        public Enter(int id, int weight) {
            this.id = id;
            this.weight = weight;
        }
    }
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer st  = new StreamTokenizer(br);
        st.nextToken();
        int n = (int)st.nval;
        st.nextToken();
        int m = (int)st.nval;
        HashMap<Integer, List<Enter>> map = new HashMap<>();
        for (int i = 0;  i < m; i++) {
            st.nextToken();
            int a = (int)st.nval;
            st.nextToken();
            int b = (int)st.nval;
            if (!map.containsKey(a)) {
                map.put(a, new ArrayList<>());
            }
            if (!map.containsKey(b)) {
                map.put(b, new ArrayList<>());
            }
            map.get(a).add(new Enter(b, 1));
            map.get(b).add(new Enter(a, 1));
        }
        //利用堆优化
        PriorityQueue<Enter> heap = new PriorityQueue<>(Comparator.comparingInt(
                    a -> a.weight));
        heap.addAll(map.get(1));
        //HashSet保存可达的路径序列（去重）
        HashSet<Integer> set = new HashSet<>();
        int flag = -1;
        set.add(1);
        //主逻辑(还可以继续优化，在主逻辑前先判断heap中是否有Enter(n,1),在可以直达的情况下避免进去主逻辑的不必要情况)
        while (!heap.isEmpty()) {
            Enter e = heap.poll();
            if (e.id == n) {
                System.out.println(e.weight);
                flag = 0;
                break;
            }
            set.add(e.id);
            if (map.containsKey(e.id)) {
                for (Enter next : map.get(e.id)) {
                    if (!set.contains(next.id)) {
                        heap.add(new Enter(next.id, e.weight + next.weight));
                    }
                }
            }
        }
        if(flag==-1) System.out.println(-1);
    }
}