Untitled

 avatar
unknown
plain_text
2 years ago
2.9 kB
3
Indexable
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Solution {
	static int N, M, K;
	static int[] DiemVs = new int[1001];
	static int[][] matrix = new int[1001][1001];
	static int[][] mtk = new int[1001][1001];
	static int[] index = new int[1001];
	static int[][] ChiPhi = new int[1001][1001];
	static int[] visit = new int[1001];
	static int ans = 0;
	static int[] vs = new int[1001];

	public static void main(String[] args) {
		try {
			System.setIn(new FileInputStream("input.txt"));
		} catch (FileNotFoundException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
		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();
			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);
			if (ans != 999999) {
				System.out.println("Case #" + (i + 1));
				System.out.println(ans);
				System.out.println();
			} else {
				System.out.println("Case #" + (i + 1));
				System.out.println(-1);
				System.out.println();
			}
		}
	}

	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;
			}
		}
	}

}
Editor is loading...