CCF201909-5:城市规划(JAVA版)（20分）

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Scanner;
public class Main{
    static int N = 2010,idx = 0,n,m;
    static int ne[] = new int[N*2];
    static int w[] = new int[N*2];
    static int e[] = new int[N*2];
    static int h[] = new int[N];
    static boolean st[] = new boolean[N];
    static boolean ve[] = new boolean[N];
    static int imp[] = new int[N];
    static int dist[] = new int[N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        Arrays.fill(h, -1);
        m = scanner.nextInt();
        int k = scanner.nextInt();//k = 2;
        int p = n-1;
        for(int i = 0 ; i < m ; i ++) {
            int x = scanner.nextInt();
            st[x] = true;
            imp[i] = x;
        }
        while(p-->0) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            add(a,b,c);add(b,a,c);
        }
        int min = 0x3f3f3f3f;
        for(int i = 0 ; i < m; i ++) {//bfs求m个点的单源最短路
            Arrays.fill(dist, 0x3f3f3f3f);
            int t = imp[i];//枚举每一个重要的点
            min = Math.min(min, bfs(t));
        }
        System.out.println(min);
        
    }
    private static int bfs(int t) {
        Arrays.fill(ve, false);
        ve[t] = true;
        int min = 0x3f3f3f3f;//单源最短路
        dist[t] = 0;
        LinkedList<Integer> q = new LinkedList<>();
        q.add(t);
        int p = m-1;
        while(p>0) {
            int head = q.poll();
            for(int i = h[head];i !=-1;i = ne[i]) {
                int j = e[i];
                if(!ve[j]) {
                    dist[j] = dist[head]+w[i];
                    q.add(j);
                    ve[j] = true;
                    if(st[j]) {
                        min = Math.min(min, dist[j]);
                        p--;
                    }
                }
            }
        }
        return min;
    }
    private static void add(int a, int b, int c) {
        e[idx] = b;ne[idx] = h[a];w[idx] = c;h[a] = idx++;
    }
}

输入：
5 3 2
1 3 5
1 2 4
1 3 5
1 4 3
4 5 1

输出：
4