Java代码

import java.util.*;

// graph和dist用long，因为设置了max_value， 一旦相加可能加出负数

public class Main{
    public static int n;
    public static int m;
    public static long[][] graph; // 记录每个边的长度
    public static long[] dist;   // 记录从起始点1到当前点的距离
    public static boolean[] checked;     // 记录距离已经被确定的点

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        graph = new long[n+1][n+1];
        dist = new long[n+1];
        checked = new boolean[n+1];

        for (long[] row : graph) Arrays.fill(row, Integer.MAX_VALUE);

        for (int i=0; i<m; i++) {
            int x = sc.nextInt();
            int y = sc.nextInt();
            graph[x][y] = Math.min(sc.nextInt(), graph[x][y]);  // 出现重边情况，保留最小值
        }

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

    public static long dijkstra() {
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[1] = 0;

        for (int i=0; i<n; i++) { // 有n个点，需要n次迭代
            // 在还未确定最短路的点中，寻找距离最小的点
            int t = -1;     // 不在checked中的，距离最短的点
            for (int j=1; j<=n; j++) {  // j代表第一个点是从1开始
                if (!checked[j] && (t==-1 || dist[j] < dist[t]))
                    t = j;
            }

            // 用t更新其它点的距离
            for (int j=1; j<=n; j++)
                dist[j] = Math.min(dist[j], dist[t]+graph[t][j]);

            checked[t] = true;
        }

        if (dist[n]>=Integer.MAX_VALUE) return -1;
        else return dist[n];
    }
}