Day59 图论part09

今天的建议依然是，一刷的时候，能了解 原理，照着代码随想录能抄下来代码就好，就算达标。

二刷的时候自己尝试独立去写，三刷的时候 才能有一定深度理解各个最短路算法。

dijkstra（堆优化版）精讲

代码随想录

超时版：

import java.util.*;public class Main{public static void main (String[] args) {//dijkstra算法三部曲//1.找到距离源节点最近的点，且未访问//2.把该点标记为已经访问//3.更新其他点到源节点的距离Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();int m = scanner.nextInt();//构造邻接表List<List<Edge>> graph = new ArrayList<>(n+1);for(int i = 0; i <= n; i++){graph.add(new ArrayList<>());}for(int i = 0; i < m; i++){int star = scanner.nextInt();int end = scanner.nextInt();int val =  scanner.nextInt();graph.get(star).add(new Edge(star, end, val));}int[] minDist = new int[n+1];Arrays.fill(minDist, Integer.MAX_VALUE);PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> Integer.compare(a[1], b[1]));boolean[] isVisited = new boolean[n+1];minDist[1] = 0;pq.add(new int[]{1,minDist[1]});// isVisited[1] = true;//找到距离源节点最近的点//把该点标记为已经访问//更新其他点到源节点的距离while(!pq.isEmpty()){int[] pair = pq.poll();int point = pair[0];if(isVisited[point]){continue;}isVisited[point] = true;for(Edge edge : graph.get(point)){if(!isVisited[edge.end