Untitled

 avatar
unknown
plain_text
2 years ago
3.5 kB
3
Indexable
import java.util.Scanner;

public class test {
    static int N, M, K;
    static int[] DiemVs;
    static int[][] matrix;
    static int[][] mtk;
    static int[] index;
    static int[][] ChiPhi;
    static int[] visit;
    static int ans;
    static int[] vs;

    static void Dijkstra(int n) {
        for (int i = 1; i <= N; i++) {
            ChiPhi[n][i] = 999999;
            visit[i] = 0;
        }
        ChiPhi[n][n] = 0;
        int minPoint;
        int minVal;
        for (int i = 1; i <= N; i++) {
            minPoint = 0;
            minVal = 999999;
            for (int j = 1; j <= N; j++) {
                if (visit[j] == 0 && ChiPhi[n][j] < minVal) {
                    minVal = ChiPhi[n][j];
                    minPoint = j;
                }
            }
            visit[minPoint] = 1;
            int tmp;
            for (int j = 0; j < index[minPoint]; j++) {
                tmp = minVal + matrix[minPoint][mtk[minPoint][j]];
                if (tmp < ChiPhi[n][mtk[minPoint][j]] && visit[mtk[minPoint][j]] == 0) {
                    ChiPhi[n][mtk[minPoint][j]] = tmp;
                }
            }
        }
    }

    static void Backtrack(int dinh, int soDiemCanDi, int chiphi) {
        if (soDiemCanDi == K) {
            if (ChiPhi[dinh][1] != 999999) {
                if (chiphi + ChiPhi[dinh][1] < ans) {
                    ans = chiphi + ChiPhi[dinh][1];
                }
            }
            return;
        }
        if (chiphi > ans) {
            return;
        }
        for (int i = 0; i <= K; i++) {
            if (vs[DiemVs[i]] == 0 && ChiPhi[dinh][DiemVs[i]] != 999999) {
                vs[DiemVs[i]] = 1;
                Backtrack(DiemVs[i], soDiemCanDi + 1, chiphi + ChiPhi[dinh][DiemVs[i]]);
                vs[DiemVs[i]] = 0;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int i = 0; i < tc; i++) {
            N = sc.nextInt();
            M = sc.nextInt();
            K = sc.nextInt();

            DiemVs = new int[K + 1];
            matrix = new int[N + 1][N + 1];
            mtk = new int[N + 1][N + 1];
            index = new int[N + 1];
            ChiPhi = new int[N + 1][N + 1];
            visit = new int[N + 1];
            vs = new int[N + 1];
            ans = 0;

            for (int j = 0; j <= N; j++) {
                DiemVs[j] = 0;
                index[j] = 0
                vs[j] = 0;
                for (int k = 0; k <= N; k++) {
                    matrix[j][k] = 999999;
                    mtk[j][k] = 0;
                }
            }

            for (int j = 1; j <= K; j++) {
                DiemVs[j] = sc.nextInt();
            }
            DiemVs[0] = 1;

            for (int j = 0; j < M; j++) {
                int r = sc.nextInt();
                int c = sc.nextInt();
                int money = sc.nextInt();
                matrix[r][c] = money;
                mtk[r][index[r]] = c;
                index[r]++;
            }

            for (int j = 0; j <= K; j++) {
                Dijkstra(DiemVs[j]);
            }

            ans = 999999;
            vs[1] = 1;
            Backtrack(1, 0, 0);

            System.out.println("Case #" + (i + 1));
            if (ans != 999999) {
                System.out.println(ans);
            } else {
                System.out.println(-1);
            }
            System.out.println();
        }
    }
}
Editor is loading...