题目描述

算法1

Java 代码

import java.util.*;
import java.io.*;

public class Main{

    static class Node{
        int x, d;
        public Node(int x, int d){
            this.x = x;
            this.d = d;
        }
    }

    static class Edge{
        int x,y,d;
        public Edge(int x, int y, int d){
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }

    static final int INF = Integer.MAX_VALUE >> 1;
    static int n,m;
    // 稀疏图 邻接表
    static List<List<Edge>> graph = new ArrayList<>();
    static int[] dist;
    static boolean[] st;
    public static void main(String[] args) throws IOException{
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split("\\s+");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        st = new boolean[n];
        dist = new int[n];
        for(int i= 0;i < n; i++){
            graph.add(new ArrayList<Edge>());
        }

        while(m--> 0){
            String[] s1 = cin.readLine().split("\\s+");
            int x = Integer.parseInt(s1[0]) - 1;
            int y = Integer.parseInt(s1[1]) - 1;
            int z = Integer.parseInt(s1[2]);
            graph.get(x).add(new Edge(x, y, z));
        }
        int[] res = dijkstra();
        int ans = res[n-1] == INF ? -1 : res[n-1];
        System.out.println(ans);
    }

    static int[] dijkstra(){
        // 初始化距离
        Arrays.fill(dist, INF);
        dist[0] = 0;
        PriorityQueue<Node> pq = new PriorityQueue<>((node1, node2) -> Integer.compare(node1.d, node2.d));
        pq.offer(new Node(0, 0));
        while(!pq.isEmpty()){
            Node t = pq.poll();
            int x = t.x;
            int d = t.d;
            if(st[x]) continue;
            st[x] = true;
            List<Edge> edges = graph.get(x);
            for (int i = 0 ; i < edges.size(); i ++){
                Edge edge = edges.get(i);
                int y = edge.y;
                if (dist[y] > dist[x] + edge.d ){
                    dist[y] = dist[x] + edge.d;
                    pq.offer(new Node(y, dist[y]));
                }
            }
        }
        return dist;

    }
}