CCF317号子任务(JAVA 30 分)

import java.util.PriorityQueue;
import java.util.Scanner;

public class Main {
    static int N = 1010,n;
    static int a[][] = new int[N][N];
    static int key[] = new int[N];
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        n = scanner.nextInt();
        int m = scanner.nextInt();
        int k = scanner.nextInt();
        int cnt = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                if (i == j)a[i][j] = 0;
                else a[i][j] = 0x3f3f3f3f;
            }
        }
        for (int i = 1; i <= n; i++) {
            int a = scanner.nextInt();
            if (a == 1)key[cnt++] = i;
        }
        while (m-- > 0) {
            int x = scanner.nextInt();
            int y = scanner.nextInt();
            int c = scanner.nextInt();
            a[x][y] = Math.min(a[x][y], c);
            a[y][x] = a[x][y];
        }
        floyd();
        PriorityQueue<Integer> q = new PriorityQueue<>(105);
        for(int i = 1; i <= n ; i ++) {
            q.clear();
            for(int j = 0; j <cnt;j++) {
                if(a[i][key[j]]!=0x3f3f3f3f) q.add(a[i][key[j]]);
            }
            if(q.size()>=k) outPath(q,k);
            else outAll(q);
        }
    }
    private static void outAll(PriorityQueue<Integer> q) {
        int res = 0;
        while(q.size()>0) {
            res+=q.poll();
        }
        System.out.println(res);
    }
    private static void outPath(PriorityQueue<Integer> q,int k) {
        int res = 0;
        for(int i =1 ; i<= k;i++) {
            res+=q.poll();
        }
        System.out.println(res);
    }
    private static void floyd() {
        for(int k = 1; k <= n; k++) {
            for(int i  = 1;  i <= n; i++) {
                for(int j = 1;j <= n; j++) {
                    a[i][j] = Math.min(a[i][j], a[i][k]+a[k][j]);
                }
            }
        }
    }
}