spfa算法 O(mn)

import java.io.*;
import java.util.*;

public class Main {

    private static int N = 810;
    private static int M = 2910;
    private static int W = 510;
    private static int[] h = new int[N];
    private static int[] e = new int[M];
    private static int[] ne = new int[M];
    private static int[] w = new int[M];
    private static int idx =0;
    private static int[] cows = new int[W];
    private static int[] dist = new int[N];
    private static boolean[] st = new boolean[N];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] s = br.readLine().split(" ");
        int n = Integer.parseInt(s[0]);
        int p = Integer.parseInt(s[1]);
        int c = Integer.parseInt(s[2]);
        Arrays.fill(h, -1);
        for (int i = 0; i < n; i++) {
            cows[i] = Integer.parseInt(br.readLine());
        }
        for (int i = 0; i < c; i++) {
            String[] ss = br.readLine().split(" ");
            int a = Integer.parseInt(ss[0]);
            int b = Integer.parseInt(ss[1]);
            int w = Integer.parseInt(ss[2]);
            add(a, b, w);
            add(b, a, w);
        }
        int ans = 0x3f3f3f3f;
        for (int i = 1; i <= p; i++) {
            spfa(i);
            int sum = 0;
            for (int j = 0; j < n; j++) {
                sum += dist[cows[j]];
                if (sum>0x3f3f3f3f)
                    break;
            }

            ans = Math.min(ans, sum);
        }
        System.out.print(ans);
    }

    private static void spfa(int i) {
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[i] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(i);
        st[i] = true;
        while (!queue.isEmpty()) {
            int t = queue.poll();
            st[t] = false;
            for (int j = h[t]; j != -1; j = ne[j]) {
                int x = e[j];
                if (dist[x] > dist[t] + w[j]) {
                    dist[x] = dist[t] + w[j];
                    if (!st[x]) {
                        queue.add(x);
                        st[x] = true;
                    }
                }
            }
        }
    }

    private static void add(int a, int b, int c) {
        e[idx] = b;
        w[idx] = c;
        ne[idx] = h[a];
        h[a] = idx++;
    }
}