java题解单源dijkstra算法

import java.util.Arrays;
import java.util.Scanner;

public class Main {
   static int N = 1005;
   static int inf = 200000005;
   static int n, m;
   static int[][] w = new int[N][N];
   static int[] dis = new int[N];
   static int[] rest = new int[N];
   static boolean[] st = new boolean[N];

   static int find() {
       int site = 0, mindis = inf;
       for (int i = 1; i <= n; i++) {
           if (!st[i] && dis[i]< mindis) {
               site = i;
               mindis = dis[i];
           }
       }
       return site;
   }

   static int dijkstra() {
       for (int i = 2; i <= n; i++)
           dis[i] = w[1][i] + rest[i];
       dis[1] = 0;
       st[1] = true;
       int now = find();
       while (now != 0) {
           for (int i = 2; i <= n; i++) {
               dis[i] = Math.min(dis[i], dis[now] + w[i][now] + rest[i]);
           }
           st[now] = true;
           now = find();
       }
       return dis[n] - rest[n];
   }

   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       n = sc.nextInt();
       m = sc.nextInt();
       if (n == 1) {
           System.out.println(0);
           return;
       }
       for (int i = 1; i <= n; i++) {
           Arrays.fill(w[i], inf);
           dis[i] = inf;
           w[i][i] = 0;
       }
       for (int i = 1; i <= n; i++)
           rest[i] = sc.nextInt();
       while (m-- > 0) {
           int x = sc.nextInt();
           int y = sc.nextInt();
           int v = sc.nextInt();
           w[x][y] = v;
           w[y][x] = v;
       }
       System.out.println(dijkstra());
   }
}