2642. 设计可以求最短路径的图类（中等）

核心思想
Dijkstra + 堆优化
模板题，每次查询做一次最短路查询即可。

class Graph {

    private List<int[]>[] nxt;

    public Graph(int n, int[][] edges) {
        nxt = new List[n];
        for(int i = 0; i < n; i++){
            nxt[i] = new ArrayList<>();
        }
        for(int[] edge: edges){
            int x = edge[0];
            int y = edge[1];
            int cost = edge[2];
            nxt[x].add(new int[]{y,cost});
        }
    }
    public void addEdge(int[] edge) {
        int x = edge[0];
        int y = edge[1];
        int cost = edge[2];
        nxt[x].add(new int[]{y,cost});
    }
    public int shortestPath(int node1, int node2) {
        int[] dis = new int[nxt.length];
        // o1 距离 o2 点
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((o1, o2) -> o1[0] - o2[0]);
        Arrays.fill(dis, Integer.MAX_VALUE);
        dis[node1] = 0;
        pq.add(new int[]{0, node1});
        while(!pq.isEmpty()){
            int[] edge = pq.poll();
            int x = edge[1];
            if(x == node2)
                return dis[x];
            for(int[] edgeTo: nxt[x]){
                int y = edgeTo[0];
                int cost = edgeTo[1];
                if(dis[y] > dis[x] + cost){
                    dis[y] = dis[x] + cost;
                    pq.add(new int[]{dis[y], y});
                }
            }
        }
        return -1;
    }
}