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

import java.util.Scanner;
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int top = 10000 * 5000;
            int n = in.nextInt();
            int m = in.nextInt();
            int[][] graph = new int[5001][5001];

            for (int i = 0; i <= 5000; i++) {
                Arrays.fill(graph[i], top);
            }

            for (int i = 0; i < m; i++) {
                int a = in.nextInt();
                int b = in.nextInt();
                int w = in.nextInt();
                graph[a][b]  = w;
                graph[b][a] = w;
            }

            int from = 1;
            int[] pathLen = new int[5001];
            for (int i = 1; i <= 5000; i++) {
                pathLen[i] = graph[from][i];
            }
            boolean[] hasvisit = new boolean[5001];
            hasvisit[1] = true;
            for (int i = 1; i <= 5000; i++) {
                int min = top;
                int k = 1;
                for (int j = 1; j <= 5000; j++) {
                    if (!hasvisit[j] && pathLen[j] < min) {
                        min = pathLen[j];
                        k = j;
                    }
                }
                hasvisit[k] = true;
                for (int j = 1; j <= 5000; j++) {
                    if (!hasvisit[j] && min + graph[k][j] < pathLen[j]) {
                        pathLen[j] = min + graph[k][j];
                    }
                }
            }
            System.out.println(pathLen[n] == top ? "-1" : pathLen[n]);
        

    }

}