Untitled

unknown
plain_text
a year ago
2.5 kB
3
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();
}
}

```