Dijkstra 朴素版

算法理解：思想是从起点开始得到距离它最近的点，这个距离就是从起点到当前点的最小值，其余的点需要通过已有的点进行不断的松弛操作。在从这个点开始不断更新点的距离，即松弛操作：当前点i距离起点的位置d[i] + 下一个距离i最短的点j 的距离g[i][j] 与 前一次j距起点的位置d[j]的较小值 便是更新之后j的最短距离

时间复杂度是O(n ^ 2)

import java.io.*;
class Main{
    static int N = 510;
    static int[][] g = new int[N][N]; // 稠密图通过邻接矩阵存储
    static int max = 0x3f3f3f3f;
    static int[] dist = new int[N]; // 从起点到i这个点的距离，开始需要初始化为max
    static boolean[] st = new boolean[N]; // 标记哪些点已经达到了最短路径
    static int n, m;
    static int dijkstra() {
        // 促使化，这里的起点即为1，那这个点的距离dist[1] = 0
        dist[1] = 0;
        for(int i = 0; i < n; i++) {
            int t = -1; // 这里的t是用来存放st[]中为false且dist[]中最小的点，即下一次进行松弛操作的点
            for (int j = 1; j <= n; j++) {
                if(!st[j] && (t == -1 || dist[t] > dist[j])) t = j;    
            }
            st[t] = true;
            for (int j = 1; j <= n; j++) {
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]); // 更新，松弛操作
            }
        }
        if (dist[n] == max) return -1;
        return dist[n];
    }
    public static void main(String[] args) throws IOException{
        BufferedReader cin = new BufferedReader(new InputStreamReader(System.in));
        String[] s = cin.readLine().split(" ");
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        // 初始化邻接矩阵
        for(int i = 0; i < N; i++) {
            dist[i] = max;  // 促使化每个点距1的距离
            for (int j = 0; j < N; j++) g[i][j] = max;
        }
        while (m-- > 0) {
            s = cin.readLine().split(" ");
            int a = Integer.parseInt(s[0]);
            int b = Integer.parseInt(s[1]);
            int c = Integer.parseInt(s[2]);
            g[a][b] = Math.min(g[a][b], c); // 防止题目中提到的有重边的情况，取较小值
        }
        System.out.println(dijkstra());
    }
}