19840 Dijkstra求最短路2

19840 Dijkstra求最短路2

相较于1，数据增强了，要用堆来优化，也就是优先队列。

⭐️难度：中等
🌟考点：Dijkstra、最短路问题
📖

📚

import java.util.*;public class Main {static int N = 100005;static int n;final static int INF = 0x3f3f3f3f;  // 一个足够大的数，同时确保不会超intstatic int[] dis = new int[N]; // 记录 点1 到每个人的最短距离static boolean[] vis = new boolean[N]; // 记录 该点是否已经被访问static ArrayList<int[]>[] g = new ArrayList[N]; // 语法注意public static void main(String[] args) {Scanner sc = new Scanner(System.in);n = sc.nextInt();int m = sc.nextInt();for (int i = 0; i < m; i++) {int a = sc.nextInt();int b = sc.nextInt();int c = sc.nextInt();addEdge(a,b,c);}dijkstra(1);System.out.println(dis[n] == INF ? -1 : dis[n]);}// 加边static void addEdge(int u, int v, int w) {if (g[u] == null) g[u] = new ArrayList<>();g[u].add(new int[]{v, w});  // 语法注意}// Dijkstrastatic void dijkstra(int s){Arrays.fill(dis,INF); // 一开始标记为 所有点都不可达dis[s] = 0;PriorityQueue<int[]> q = new PriorityQueue<>(Comparator.comparingInt(e->e[1]));  // 比较数组的第二个元素，也就是边的权值，注意语法q.add(new int[]{s,0}); // 注意语法while(!q.isEmpty()){int[] cur = q.poll(); // 优先队列已经把权值按升序排好，只管取队头int u = cur[0];if(vis[u] == true) continue; // 若该店访问过，跳过vis[u] = true; // 标记为已访问if(g[u] == null) continue; // 改 点u 没有可指向边，跳过for(int[] e : g[u]){int v = e[0];  // 取点int w = e[1];  // 取权值if(dis[v] > dis[u] + w){dis[v] = dis[u] + w; // 刷新 点1 到 点v 的最近距离q.add(new int[]{v,dis[v]}); // 与 点u 相连的点入队列}}}}
}

🍎笔记