记录编号	157534	评测结果	AAAAAAAAAA
题目名称	[USACO Jan15] 牛的路线2	最终得分	100
用户昵称	TA	是否通过	通过
代码语言	C++	运行时间	0.033 s
提交时间	2015-04-09 11:02:24	内存使用	1.52 MiB

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
using namespace std;
inline void in(int &x){
	char c=getchar();
	while(c<'0'||c>'9')c=getchar();
	x=0;
	for(;c>='0'&&c<='9';c=getchar())x=x*10+(c^48);
}
#include<bitset>
bitset<10005> p[505][2];//航线i，有无j，0表示在A之后，1表示在B之前。 
int main(){
	freopen("cowrouteb.in","r",stdin);
	freopen("cowrouteb.out","w",stdout);
	int A,B,N;
	in(A),in(B),in(N);
	int c[505],i,j,son[505],flag[505];//00表示无A无B,10表示只有A，01表示只有B，11表示既有A，又有B。 
	for(i=0;i<N;++i){
		in(c[i]),in(son[0]);
		for(j=1;j<=son[0];++j)in(son[j]);
		for(j=1;j<=son[0];++j)
			if(son[j]==A){
				flag[i]|=2;
				break;
			}
		while(++j<=son[0])p[i][0][son[j]]=1;
		for(j=son[0];j;--j)
			if(son[j]==B){
				flag[i]|=1;
				break;
			}
		while(--j>0)p[i][1][son[j]]=1;
	}
	int ans=0x7fffffff;
	bitset<10005> tmp;
	for(i=0;i<N;++i)
		if(flag[i]&2)
			for(j=0;j<N;++j)
				if(flag[j]&1&&(i==j?c[i]:c[i]+c[j])<ans&&(p[i][0]&p[j][1]).any())
					ans=i==j?c[i]:c[i]+c[j];
	printf("%d\n",ans==0x7fffffff?-1:ans);
}