Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
3.7 kB
1
Indexable
Never
import java.util.Scanner;

public class test {
    static int N, M, K;
    static int[] DiemVs;
    static int[][] matrix;
    static int[][] mtk;
    static int[][] ChiPhi;
    static boolean[] visited;
    static int ans;

    static void Dijkstra(int n) {
        visited[n] = true;
        ChiPhi[n][n] = 0;

        for (int i = 1; i <= N; i++) {
            int minDist = Integer.MAX_VALUE;
            int minVertex = -1;

            for (int j = 1; j <= N; j++) {
                if (!visited[j] && ChiPhi[n][j] < minDist) {
                    minDist = ChiPhi[n][j];
                    minVertex = j;
                }
            }

            if (minVertex == -1)
                break;

            visited[minVertex] = true;

            for (int j = 1; j <= N; j++) {
                if (!visited[j] && matrix[minVertex][j] != 999999) {
                    int newDist = minDist + matrix[minVertex][j];
                    if (newDist < ChiPhi[n][j]) {
                        ChiPhi[n][j] = newDist;
                    }
                }
            }
        }
    }

    static void Backtrack(int vertex, int numVerticesVisited, int cost) {
        if (numVerticesVisited == K) {
            if (ChiPhi[vertex][1] != 999999) {
                if (cost + ChiPhi[vertex][1] < ans) {
                    ans = cost + ChiPhi[vertex][1];
                }
            }
            return;
        }
        if (cost > ans) {
            return;
        }
        for (int i = 0; i <= K; i++) {
            int nextVertex = DiemVs[i];
            if (!visited[nextVertex] && ChiPhi[vertex][nextVertex] != 999999) {
                visited[nextVertex] = true;
                Backtrack(nextVertex, numVerticesVisited + 1, cost + ChiPhi[vertex][nextVertex]);
                visited[nextVertex] = false;
            }
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int tc = sc.nextInt();
        for (int t = 1; t <= tc; t++) {
            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];
            ChiPhi = new int[N + 1][N + 1];
            visited = new boolean[N + 1];
            ans = Integer.MAX_VALUE;

            for (int i = 0; i <= N; i++) {
                for (int j = 0; j <= N; j++) {
                    matrix[i][j] = 999999;
                    ChiPhi[i][j] = 999999;
                }
            }

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

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

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

            visited[1] = true;
            Backtrack(1, 0, 0);

            System.out.println("Case #" + t);
            if (ans != Integer.MAX_VALUE) {
                System.out.println(ans);
            } else {
                System.out.println(-1);
            }
            System.out.println();
        }
    }

    static class Node implements Comparable<Node> {
        int vertex;
        int distance;

        public Node(int vertex, int distance) {
            this.vertex = vertex;
            this.distance = distance;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.distance, other.distance);
        }
    }
}