题目描述

如题

样例

blablabla

算法1

堆优化的DJ思特拉 $O(mlog(n))$

时间复杂度

参考文献

Java 代码

import java.io.*;
import java.util.*;
public class Main{
    public static Node[] nodes;
    public static int[] dist;
    public static boolean[] visited;
    public static void main(String[] args) throws IOException{
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        String[] line0 = reader.readLine().split(" ");
        int n = Integer.parseInt(line0[0]);
        int m = Integer.parseInt(line0[1]);

        nodes = new Node[n + 1];
        for(int i = 1; i < n + 1; i++){
            nodes[i] = new Node(i);
        }
        dist = new int[n + 1];
        visited = new boolean[n + 1];
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[1] = 0;
        while(m-- > 0){
            String[] line = reader.readLine().split(" ");
            int a = Integer.parseInt(line[0]);
            int b = Integer.parseInt(line[1]);
            int w = Integer.parseInt(line[2]);
            add(a, b, w);
        }


        PriorityQueue<Node> q = new PriorityQueue<>(n + 1);
        q.offer(nodes[1]);
        while(!q.isEmpty()){
            Node temp = q.poll();
            visited[temp.val] = true;
            if(temp.val == n){
                break;
            }
            for(Map.Entry<Node, Integer> entry : temp.neigh.entrySet()){
                Node node = entry.getKey();
                int val = node.val;
                int wei = entry.getValue();

                if(visited[entry.getKey().val]){
                    continue;
                }
                // 更新距离, 入队
                if(dist[val] > dist[temp.val] + wei){
                    dist[val] = dist[temp.val] + wei;
                    q.offer(entry.getKey());  // 这句话一定要写在if里面
                }

            }
        }
        if(dist[n] == 0x3f3f3f3f){
            System.out.println(-1);
        }else{
            System.out.println(dist[n]);
        }
        // System.out.println(Arrays.toString(dist));

    }

    public static void add(int a, int b, int weight){
        if(a == b){
            return;
        }
        int oriWei = nodes[a].neigh.getOrDefault(nodes[b], 0x3f3f3f3f);
        if(weight < oriWei){
            nodes[a].neigh.put(nodes[b], weight);
        }
    }

    static class Node implements Comparable<Node>{
        public int val;
        public Map<Node, Integer> neigh; 
        public Node(int i){
            this.val = i;
            neigh = new HashMap<>();
        }

        @Override 
        public int compareTo(Node e){
            return dist[this.val] - dist[e.val];
        }
    }
}