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

import java.util.*;
public class Main {
    public static final int N = 50000 * 10000 + 1;
    static int[][] edges = new int[5001][5001];
    static int[] length = new int[5001];
    static boolean[] visited = new boolean[5001];

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int m = input.nextInt();

        int start;
        int end;
        int weight;
        for (int[] ints : edges) {
            Arrays.fill(ints, N);
        }

        for (int i = 0; i < m; i++) {
            start = input.nextInt();
            end = input.nextInt();
            weight = input.nextInt();
            edges[start][end] = weight;
            edges[end][start] = weight;
        }
        //定义数组表示到1号点到所有点的距离，默认除了到自己是0外，到其他点的距离都是N

        Arrays.fill(length, N);
        length[1] = 0;
        visited[1] = true;
        updateWay(1);
        for (int i = 1; i < 5001; i++) {
            start = getStart();
            if (start == n) {
                System.out.println(length[start]);
                break;
            }
            if (start != 0) {
                updateWay(start);
            }
        }
        if (!visited[n]) {
            System.out.println(-1);
        }

    }

    public static int getStart() {
        int min = N;
        int start = 0;
        for (int i = 1; i < 5001; i++) {
            if (!visited[i]) {
                //如果这个点还没设为已访问
                if (length[i] < min) {
                    //如果这个点的路径已被更新且更小
                    start = i;
                    min = length[i];
                }
            }
        }
        visited[start] = true;
        //System.out.println("目前可到达的未访问点，" +start+ "距离最近");
        return start;
    }

    //遍历边集，找出各个与start直接相连的未访问点，将距离更新,并将其设为已访问
    public static void updateWay(int start) {
        for (int i = 1; i < 5001; i++) {
            if (!visited[i]) {
                if (length[i] > length[start] + edges[start][i]) {
                    //System.out.printf("%d与%d相连，距离从%d更新为%d\n",start,i,length[i],length[start] + edges[start][i]);
                    length[i] = length[start] + edges[start][i];

                }
            }
        }
    }
}