Untitled
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...