Dijkstra 堆优化版

通过堆能实现每次从未被确定最短的点中以logn的时间复杂度获得最小值

时间复杂度为mlogn

import java.io.*;
import java.util.*;
class Main{
    static int N = 150010;
    static int n, m, idx;
    static int max = 0x3f3f3f3f;
    static boolean[] st = new boolean[N];
    static int[] h = new int[N], w = new int[N], e = new int[N], ne = new int[N];  //稀疏图使用邻接表存储
    static int[] dist = new int[N];
    static class Place {
        int x, y;// 分别代表节点，和对应距离起点的距离
        Place(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
    static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
    static int dijkstra(){
        dist[1] = 0;
        PriorityQueue<Place> q = new PriorityQueue<>(n, (a, b) -> a.y - b.y);  // 优先队列，初始化大小n, 规定比较规则
        q.offer(new Place(1, 0));
        while(!q.isEmpty()) {
            Place p = q.poll();
            int ver = p.x, distance = p.y;
            if(st[ver]) continue;
            st[ver] = true;  //存在的目的是减低时间复杂度避免重复遍历
            for (int i = h[ver]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] > distance + w[i]) {
                    dist[j] = distance + w[i];
                    q.offer(new Place(j, dist[j]));
                }
            }
        }
        if (dist[n] == max) return -1;
        return dist[n];
    }
    public static void main(String[] args) throws IOException {
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        for(int i = 0; i < N; i++) {
            dist[i] = max;
            h[i] = -1;
        }
        while (m-- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            add(a, b, c);
        }
        System.out.println(dijkstra());
    }
}