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

import java.util.*;
import java.lang.*;
class Main {
    static int N = 100010;
    //邻接表存储
    static int[]h;
    static int[]e;
    static int[]ne;
    static int[]w;
    static int idx; //每一条边(指针)的编号
    static void addEdge(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int[] dist;//每个店到1号点的距离，下标从1开始
    static boolean[] st;//是否已经确定最短路的集合
    static void init(int n, int m) {
        //邻接表存储
        idx = 0;
        h = new int [N];
        e = new int [N];
        ne = new int [N];
        w = new int [N];
        //初始化所有未确定到源点的最小距离的点 为正无穷
        dist = new int [N];
        Arrays.fill(dist, 0x3f3f3f3f);
        st = new boolean [N];
        //初始化邻接表的表头
        Arrays.fill(h, -1);
        //读入边
        while (m-- > 0){
            int a, b, c;
            addEdge(a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt());
            addEdge(b,a,c);
        }
    }
    static int dijkstra(int n, int m) {
        //1.init
        init(n, m);
        //2.calc
        class Pair {
            final int distance; //距离
            final int ver;      //编号
            public Pair(int _v1, int _v2) {
                this.distance = _v1;
                this.ver = _v2;
            }
        }
        //小根堆
        Queue<Pair> q = new PriorityQueue<Pair>(n, new Comparator<Pair>() {
            @Override
            public int compare(Pair o1, Pair o2) {
                return o1.distance - o2.distance;
            }
        });
        Pair start;
        q.add((start = new Pair(0, 1)));
        dist[start.ver] = start.distance;
        while (!q.isEmpty()) {
            Pair p = q.poll();
            if (st[p.ver]) continue;
            st[p.ver] = true;
            //更新t相连的边到1号点最小距离
            for (int i = h[p.ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > w[i] + p.distance) {
                    dist[j] = w[i] + p.distance;
                    q.add(new Pair(dist[j], j));
                }
            }
        }
        return dist[n] == 0x3f3f3f3f ? -1 : dist[n];
    }
    static Scanner sc = new Scanner(System.in);
    public static void main(String[]args) {
        System.out.println(dijkstra(sc.nextInt(), sc.nextInt()));
    }
}