记录编号	76435	评测结果	AAAAAAAAA
题目名称	篱笆回路	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.025 s
提交时间	2013-10-30 19:31:34	内存使用	0.63 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
#include<vector>
#include<cstring>
#include<iomanip>
using namespace std;
const int SIZEF=101;
const int SIZEN=201;
const int INF=0x7ffffff;
class FENCE{
public:
	int pos;
	int len;
	int n1,n2;
	vector<int> cn1;
	vector<int> cn2;
	int p1,p2;
	FENCE(){
		cn1.clear();cn2.clear();
		p1=p2=0;
	}
	int findep(int);
	void mergev(void);
	void addedge(void);
};
FENCE fc[SIZEF];
int numfc;
int n;
int ufs[SIZEN]={0};
int dist[SIZEN][SIZEN]={0};
int grand(int x){
	if(ufs[x]==0) return x;
	int ans=grand(ufs[x]);
	ufs[x]=ans;
	return ans;
}
void leafmerge(int x,int y){//将x,y所在的两个并查集合并
	int gx=grand(x),gy=grand(y);
	if(gx!=gy){
		ufs[gx]=gy;
	}
}
int FENCE::findep(int x){//寻找和x相连的是1端还是2端
	if(find(cn1.begin(),cn1.end(),x)!=cn1.end()) return 1;
	return 2;
}
void FENCE::mergev(void){
	int i;
	int u;
	int k,kp;
	for(i=0;i<n1;i++){
		u=cn1[i];
		k=fc[u].findep(pos);
		kp=(k==1?fc[u].p1:fc[u].p2);
		leafmerge(p1,kp);
	}
	for(i=0;i<n2;i++){
		u=cn2[i];
		k=fc[u].findep(pos);
		kp=(k==1?fc[u].p1:fc[u].p2);
		leafmerge(p2,kp);
	}
}
void mergev(void){
	int i;
	for(i=1;i<=numfc;i++) fc[i].mergev();
}
void single_addedge(int a,int b,int len){
	dist[a][b]=dist[b][a]=len;
}
void FENCE::addedge(void){
	single_addedge(grand(p1),grand(p2),len);
}
void addedge(void){
	int i;
	for(i=1;i<=numfc;i++) fc[i].addedge();
}
void transform(void){
	mergev();
	addedge();
}
void init(void){
	scanf("%d",&numfc);
	int i,j,x;
	for(i=1;i<=numfc;i++){
		FENCE temp;
		scanf("%d%d%d%d",&temp.pos,&temp.len,&temp.n1,&temp.n2);
		for(j=1;j<=temp.n1;j++){
			scanf("%d",&x);
			temp.cn1.push_back(x);
		}
		for(j=1;j<=temp.n2;j++){
			scanf("%d",&x);
			temp.cn2.push_back(x);
		}
		temp.p1=2*temp.pos-1,temp.p2=2*temp.pos;
		fc[temp.pos]=temp;
	}
	n=2*numfc;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			dist[i][j]=INF;
		}
		dist[i][i]=0;
	}
}
int ans=INF;
int f[SIZEN][SIZEN]={0};
void floyd(void){
	int i,j,k;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++) f[i][j]=dist[i][j];
	}
	for(k=1;k<=n;k++){
		for(i=1;i<=k-1;i++){
			for(j=i+1;j<=k-1;j++){
				ans=min(ans,f[i][j]+dist[i][k]+dist[k][j]);
			}
		}
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++) f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
		}
	}
}
int main(){
	freopen("fence6.in","r",stdin);
	freopen("fence6.out","w",stdout);
	init();
	transform();
	floyd();
	printf("%d\n",ans);
	return 0;
}