Untitled
plain_text
17 days ago
3.5 kB
1
Indexable
Never
package tuan_trang_mat; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static int n, m, k, check; static long res; static int[][] a; static int[] vitri, visit, comb, visithv, parent; static long[][] kc; static void cal_distan() { kc = new long[n + 1][n + 1]; for (int i = 0; i <= k; i++) { int[] q = new int[10000]; long[][] lan = new long[n + 1][n + 1]; int front = 0, rear = 1; q[front] = vitri[i]; visit = new int[n + 1]; visit[vitri[i]] = 1; parent = new int[n+1]; while (front < rear) { int x = q[front]; visit[x] = 2; for (int j = 1; j <= n; j++) { if (a[x][j] > 0 && visit[j] == 0) { q[rear] = j; rear++; lan[vitri[i]][j] = lan[vitri[i]][x] + a[x][j]; visit[j] = 1; }else if (a[x][j] > 0 && visit[j] == 1 && lan[vitri[i]][j] > lan[vitri[i]][x] + a[x][j]) { lan[vitri[i]][j] = lan[vitri[i]][x] + a[x][j]; }else if (a[x][j] > 0 && visit[j] == 2 && lan[vitri[i]][j] > lan[vitri[i]][x] + a[x][j]) { q[rear] = j; rear++; lan[vitri[i]][j] = lan[vitri[i]][x] + a[x][j]; } } front++; } for (int j = 1; j <= n; j++) { kc[vitri[i]][j] = lan[vitri[i]][j]; } } } static void backtrack(int count, long chiphi){ if(count == k +1 ){ // for(int i = 0; i <=k ; i++){ // System.out.print(comb[i] + " "); // } // System.out.println(); long x = chiphi + kc[comb[count-1]][1]; // System.out.println("k " + count + " " + kc[comb[count-1]][1]); // for(int i = 1; i <= k;i++) if(x < res) { // check =1; res = x; } return; } if(chiphi >= res){ return; } for(int i = 1; i <= k ; i++){ if(visithv[i] == 0){ visithv[i] = 1; comb[count] = vitri[i]; if(kc[comb[count-1]][comb[count]] == 0){ check = 0; return; } // System.out.println((count +1) + " kc " + kc[comb[count-1]][comb[count]]); backtrack(count +1 , chiphi + kc[comb[count-1]][comb[count]]); visithv[i] = 0; } } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input(ttm).txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } Scanner scanner = new Scanner(System.in); int test = scanner.nextInt(); for (int t = 1; t <= test; t++) { n = scanner.nextInt(); m = scanner.nextInt(); k = scanner.nextInt(); vitri = new int[k+1]; vitri[0] = 1; for (int i = 1; i <= k; i++) { vitri[i] = scanner.nextInt(); } a = new int[n + 1][n + 1]; for (int i = 0; i < m; i++) { a[scanner.nextInt()][scanner.nextInt()] = scanner.nextInt(); } // for (int i = 0; i <= k; i++) { // System.out.print(vitri[i] + " "); // } // System.out.println(); check = 1; res = Long.MAX_VALUE; cal_distan(); // for(int i = 1; i <=n;i++){ // for(int j=1;j<=n;j++){ // System.out.print(kc[i][j] + " "); // } // System.out.println(); // } visithv = new int[k+1]; comb = new int[k+1]; comb[0] = 1; backtrack(1, 0); if(check == 0){ System.out.println("Case #" + t + "\n-1\n" ); }else{ System.out.println("Case #" + t + "\n" + res+"\n"); } } scanner.close(); } }