当前位置：首页 > article >正文

Day59 图论part09

article 2025/1/2 22:43:42

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

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

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

查看全文

http://www.kler.cn/a/457937.html