题解 | #【模板】单源最短路2#

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

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] lines = reader.readLine().split(" ");
        int v = Integer.parseInt(lines[0]);
        int e = Integer.parseInt(lines[1]);

        int[][] graph = new int[5000][5000];//为了不越界只能定义最大的图
        for (int i = 0; i < 5000; i++) {
            Arrays.fill(graph[i], Integer.MAX_VALUE);
        }
        int begin, end, weight;
        for (int i = 0; i < e; i++) {
            lines = reader.readLine().split(" ");
            begin = Integer.parseInt(lines[0]);
            end = Integer.parseInt(lines[1]);
            weight = Integer.parseInt(lines[2]);
            //把点和对应权值添加到图中
            graph[begin - 1][end - 1] = weight;
            graph[end - 1][begin - 1] = weight;
        }
        reader.close();

        int[] res = dijkstra(graph);
        //writer.write(Arrays.toString(res));
        if (res[v - 1] != Integer.MAX_VALUE)
            writer.write(res[v - 1] + "");
        else
            writer.write(-1 + "");

        writer.close();
    }

    public static int[] dijkstra(int[][] graph) {
        //定义路径数组,dist[i]为到点m对应下标i的最短距离
        int[] dist = new int[graph.length];
        //初始化无穷大
        Arrays.fill(dist, Integer.MAX_VALUE);

        //定义状态数组
        boolean[] state = new boolean[graph.length];
        Arrays.fill(state, false);

        //起始点的路径设置为0
        dist[0] = 0;

        //优先队列处理点
        PriorityQueue<Integer> q = new PriorityQueue<>(Comparator.comparingInt(v -> dist[v]));
        q.add(0);

        while (!q.isEmpty()) {
            int u = q.poll();
            state[u] = true;

		  //算法核心
            for (int i = 0; i < graph.length; i++) {
                if (!state[i] && graph[u][i] != Integer.MAX_VALUE &&
                        (dist[u] + graph[u][i]) < dist[i]) {
                    dist[i] = dist[u] + graph[u][i];
                    q.add(i);
                }
            }
        }
        return dist;
    }
}