题解 | JAVA Dijkstra#单源最短路# [P2-T2]

就标准Dijkstra

import java.util.*;

public class Solution {
    // shortest path from 1 to n.
    public int findShortestPath (int n, int m, int[][] graph) {
      // {u: [{v1, w2}, [v2, w2], ...]}
      Map<Integer, List<int[]>> edges = new HashMap<>();
      for(int[] edge : graph) {
        if (!edges.containsKey(edge[0])) 
          edges.put(edge[0], new ArrayList<int[]>());
        edges.get(edge[0]).add(new int[]{edge[1], edge[2]});
      }
      
      // int[]{to, curDist}
      PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1]-b[1]);
      // {to: dist}
      Map<Integer, Integer> distMap = new HashMap<>();
      minHeap.offer(new int[]{1, 0});
      
      while (!minHeap.isEmpty()) {
        int[] min = minHeap.poll();
        int to = min[0], dist = min[1];
        if (to == n) return dist;  // dist to n found
        
        if (distMap.containsKey(to)) continue;  // dist for to already calculated
        else distMap.put(to, dist);
          
        if (!edges.containsKey(to)) continue;  // no out-going edge
        for (int[] edge : edges.get(to)) {
          if (!distMap.containsKey(edge[0]))
            minHeap.offer(new int[]{edge[0], dist + edge[1]});
        }
      }
      
      return -1; // n not reachable from 1
    }
}