Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.7 kB
0
Indexable
Never
#include <stdio.h>
#include <iostream>

using namespace std;
int const max_size =105;
int const  vc=1000000;
int mayBD[max_size];
int A[max_size][max_size];  // luu lai matran ke
int visit[max_size];
int n;             // so thanh
int ans;
bool flag;        // tim dc chu trinh hay chua

void reset(){  // rset visit de dfs
	for(int i=0; i<n;i++){
		visit[i]=0;
	}
}

void dfs(int tempThanh, int thanh, int sl,int tempMin, int d1, int d2){
	if( tempThanh==thanh && sl>=3) {
		flag=true;
		ans+=tempMin;
		A[d1][d2]=0;
		A[d2][d1]=0;
		return;

	}
	for(int col =0; col<n; col ++){
		if(flag) return ;
		if(A[tempThanh][col]==1 &&(!visit[col]||( col==thanh && sl>=3))) {
			visit[col]=1;
			int value =mayBD[tempThanh]+mayBD[col];
			if( tempMin> value) {
				dfs(col, thanh,sl+1, value,tempThanh,col);
			}else
			{
				dfs(col, thanh,sl+1,tempMin,d1,d2);
			}
		}
	}
}

void solve(){
	for(int thanh=0; thanh<n; thanh++){
		reset();// duyet cac thanh de dfs
		visit[thanh]=1;
		flag=false;
		dfs(thanh,thanh,1,vc,-1,-1);
		while(flag){
			reset();
			visit[thanh]=1;	
			flag=false;
			dfs(thanh,thanh,1,vc,-1,-1);
		}

	}
}



int main(int argc, char** argv)
{
	int tc, T;

	// The freopen function below opens input.txt file in read only mode, and afterward,
	// the program will read from input.txt file instead of standard(keyboard) input.
	// To test your program, you may save input data in input.txt file,
	// and use freopen function to read from the file when using cin function.
	// You may remove the comment symbols(//) in the below statement and use it.
	// Use #include<cstdio> or #include<stdio.h> to use the function in your program.
	// But before submission, you must remove the freopen function or rewrite comment symbols(//).

	freopen("text.txt", "r", stdin);

	cin >> T;
	for(tc = 1; tc <= T; tc++)
	{
		cin>>n;
		// reset
		for(int i=0; i<n;i++){           
			for(int j=0; j<n;j++){
				A[i][j]=0;
			}
		}
		int thanh,slke, soMayBD, tempThanh;
		
		for(int i=0; i<n;i++){
			cin>>thanh>>soMayBD>>slke;
			mayBD[thanh]=soMayBD;
			for(int k=0; k<slke; k++){
				cin>>tempThanh;
				A[thanh][tempThanh]=1;
				A[tempThanh][thanh]=1;
			}

		}
		ans=0;
		solve();
		cout<<ans<<endl;

	}

	return 0;//Your program should return 0 on normal termination.
}


3

3

0 1 2

1 2

1 2 2

0 2

2 3 2

0 1

7

0 1 2

2 3

1 2 2

3 4

2 3 2

0 5

3 1 4

0 1 5 6

4 2 2

1 6

5 3 2

2 3

6 1 2

3 4

4

0 1 2

1 2

1 8 2

0 3

2 16 2

0 3

3 12 2

1 2


out 
3

4

9