Untitled
plain_text
a month ago
2.5 kB
1
Indexable
Never
package tan_cong_thanh_tri; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.util.Scanner; public class Solution { static boolean w; static int n, result; static int[][] a; static int[] visit=new int[101]; static int[] may=new int[101]; public static void duyet(int dau, int cuoi, int truoc, int minx, int miny, int min){ visit[cuoi] = 1; for(int i = 0; i < n; i++){ if(visit[i] == 0 && w == false){ if(may[cuoi] + may[i] < min){ duyet(dau, i, cuoi, cuoi, i, may[cuoi] + may[i]); }else{ duyet(dau, i, cuoi, minx, miny, min); } } if(i == dau && i != truoc && visit[i] == 1){ if(may[cuoi]+may[i]<min){ minx = cuoi; miny = i; min = may[cuoi] +may[i]; } result += min; a[minx][miny] = 0; a[miny][minx] = 0; w = true; return; } } } public static void DFS(int dau, int cuoi, int truoc, int minx, int miny, int min){ visit[cuoi] = 1; // System.out.println(y); for(int i = 0; i < n; i++){ if(a[cuoi][i] == 1 && w==false){ if(visit[i] == 0 && i != truoc){ if(may[cuoi]+may[i]<min){ DFS(dau,i,cuoi,cuoi,i,may[cuoi]+may[i]); }else{ DFS(dau,i,cuoi,minx,miny,min); } } if(i == dau && i!=truoc && visit[i]==1){ if(may[cuoi]+may[i]<min){ minx=cuoi; miny=i; min=may[cuoi]+may[i]; } result+=min; a[minx][miny]=0; a[miny][minx]=0; w=true; return; } } } } public static void main(String[] args) { try { System.setIn(new FileInputStream("input.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++) { // input n = scanner.nextInt(); a = new int[n][n]; for (int i = 0; i < n; i++) { int m = scanner.nextInt(); may[m] = scanner.nextInt(); int k = scanner.nextInt(); for (int j = 0; j < k; j++) { int x = scanner.nextInt(); a[m][x] = 1; a[x][m] = 1; } } result = 0; for(int i=0;i<n;i++){ for(int j=0;j<n;j++) visit[j]=0; w=false; visit[i]=1; DFS(i,i,i,i,i,15000); if(w==true) i--; } System.out.println("Case #" + t + "\n" + result); } scanner.close(); } }