算法

参考视频：https://www.bilibili.com/video/BV1zz4y1m7Nq?from=search&seid=10333953268212004858
注意：
① 3个变量的含义： g[][] dist[] st[]
1)g[][] 存储权值
2)dist[i] i到原点的距离
3)st[i] i点是否求得最短距离了（这个最难理解，什么时候算是求得了最短距离呢？如果当前点是剩余的没做为“原点”的点中dist[i]最小的点，那么其就会被标记成求得过最短距离了。此种情况不可能存在“曲线救国”情况使得该点到原点距离更小。）

public static int dijkstra(){
    Arrays.fill(dist,0x3f3f3f3f);
    dist[1] = 0;

    for(int i = 0; i < n; i++){
        int t = -1;
        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++){
            // 这里不需要有筛选t的临边语句了，因为对于非t的临边j，那么g[t][j] = 0x3f3f3f3f; 
            // 对于非t的临边，如果dist[j] 有值那么Math.min()结果还是dist[j],如果dist[j]值是0x3f3f3f3f还是dist[j]
            dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
        }
    }
    return dist[n] == 0x3f3f3f3f? -1 :dist[n];
}

// 完整代码
import java.util.*;

public class Main{
    static int N = 510;
    static int m, n;
    static int[][] g = new int[N][N];
    static int[] dist = new int[N];
    static boolean[] st = new boolean[N];

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

        // 因为有重边，但是权重不同，要取最小值，那么先给它赋值一个大值。
        for(int i = 1; i <=n; i++) Arrays.fill(g[i], 0x3f3f3f3f);
        while(m-->0){
            int a= sc.nextInt(), b = sc.nextInt(), c = sc.nextInt();
            g[a][b] = Math.min(g[a][b], c);
        }

        System.out.print(dijkstra());
    }

    public static int dijkstra(){
        Arrays.fill(dist,0x3f3f3f3f);
        dist[1] = 0;

        for(int i = 0; i < n; i++){
            int t = -1;
            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++){
                // 这里不需要有筛选t的临边语句了，因为对于非t的临边j，那么g[t][j] = 0x3f3f3f3f; 
                // 对于非t的临边，如果dist[j] 有值那么Math.min()结果还是dist[j],如果dist[j]值是0x3f3f3f3f还是dist[j]
                dist[j] = Math.min(dist[j], dist[t] + g[t][j]);
            }
        }
        return dist[n] == 0x3f3f3f3f? -1 :dist[n];
    }
}