堆优化版Dijkstra

问题

解决这样一类问题，起点确定的，可以有重边和自环的，各边权都为正数的稀疏图的最短路问题

要素

1. h[], idx, e[], ne[], w[] 用邻接表存储图
2. st[]记录已经确定最短距离的点
3. dist[] 存储每个点到起点的最短距离

   思路

   相较与朴素版Dijkstra每次遍历一遍所有节点找到当前距起点最近的点，堆优化版优化了这一做法，有点类似bfs，每次的队头元素如果还没加入st的话，一定是当前距起点最近的点，用该点更新其临点到起点的距离并入队，因为是优先队列，每次加入一个元素会更新队列使得最小元素出现在队头。

时间复杂度：手写堆：O(M*logN)，优先队列：O(M*logM) = O(MlogN2) = O(MlogN)
所以没必要手写堆
本质：贪心

模板

850. Dijkstra求最短路 II
给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。
请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n号点，则输出 −1。
输入格式
第一行包含整数 n和 m。
接下来 m行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y的有向边，边长为 z。
输出格式
输出一个整数，表示 1号点到 n 号点的最短距离。
如果路径不存在，则输出 −1。
数据范围
1≤n,m≤1.5×105
图中涉及边长均不小于 0，且不超过 10000。
输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

import java.util.*;
public class Main {
    static final int N = 150010;
    static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];
    static int n, m;
    static int idx = 0;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        Arrays.fill(h, -1);
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            add(a, b, c);
        }
        dijkstra(1, dist);
        if (dist[n] == 0x3f3f3f3f)
            System.out.println(-1);
        else
            System.out.println(dist[n]);
    }
    static void dijkstra(int start, int[] dist) {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[start] = 0;
        Arrays.fill(st, false);
        PriorityQueue<int[]> q = new PriorityQueue<>((o1, o2) -> (o1[1] - o2[1]));
        q.offer(new int[]{start, 0});
        while (!q.isEmpty()) {
            int[] p = q.poll();
            int u = p[0], d = p[1];
            if (st[u]) continue;
            st[u] = true;
            dist[u] = d;
            for (int i = h[u]; i != -1; i = ne[i]) {
                int j = e[i], ww = w[i];
                q.offer(new int[]{j, ww + d});
            }
        }
    }
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}