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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    //存储到达终点前的一个点
    private static int[] path;
    //存储1号点到终点的最短路径长度
    private static int[] path_len;
    //不可达距离
    public static int MaxValue = 500000001;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //加快读入（要注意使用范围，否则会精度损失）
        StreamTokenizer st = new StreamTokenizer(br);

        //st.nval返回的是一个double类型的值
        st.nextToken();
        int n = (int) st.nval;
        st.nextToken();
        int m = (int) st.nval;

        path = new int[5001];
        path_len = new int[5001];
        //存储图中边的信息并初始化为不可达
        int[][] graph = new int[5001][5001];
        for (int[] c : graph) {
            Arrays.fill(c, MaxValue);
        }
        //从输入流读入边的信息
        for (int i = 0; i < m; i++) {
            st.nextToken();
            int u = (int) st.nval;
            st.nextToken();
            int v = (int) st.nval;
            st.nextToken();
            int len = (int) st.nval;
            graph[u][v] = len;
            graph[v][u] = len;
        }
        shortestPath_Dijkstra(1, 5000, graph);
        if (path_len[n] == MaxValue)
            System.out.println(-1);
        else
            System.out.println(path_len[n]);

    }

    //u为起始点，n是顶点个数，graph是存储的图信息。
    private static void shortestPath_Dijkstra(int u, int n, int[][] graph) {
        //表示是否确定好最短路径
        boolean[] flag = new boolean[n + 1];

        int min = 0, k = 0;
        //u到其他顶点的直接距离
        for (int i = 1; i <= n; i++) {
            flag[i] = false;
            path_len[i] = graph[u][i];
            path[i] = 1;
        }

        flag[u] = true;
        path[u] = 1;
        path_len[u] = 0;

        for (int i = 1; i < n; i++) {//将其他n-1个可能达到的顶点加入路径
            min = MaxValue;
            for (int j = 1; j <= n; j++) {
                if (!flag[j] && path_len[j] < min) {
                    min = path_len[j];
                    k = j;
                }
            }
            //将距离最短的顶点k加入路径并更新可达路径
            flag[k] = true;
            for (int j = 1; j <= n ; j++) {
                if (!flag[j] && (min + graph[k][j]) < path_len[j]) {
                    path_len[j] = min + graph[k][j];
                    path[j] = k;
                }
            }
        }
    }
}