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

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
int s,t,m,ans=inf;
int a[501],ds[10001],dt[10001];
int main(){
	freopen("cowrouteb.in","r",stdin);
	freopen("cowrouteb.out","w",stdout);
	scanf("%d%d%d",&s,&t,&m);
	memset(ds,0x3f,sizeof ds);
	memset(dt,0x3f,sizeof dt);
	ds[s]=dt[t]=0;
	for(int c,k,i=1;i<=m;i++){
		scanf("%d%d",&c,&k);
		for(int j=1;j<=k;j++) scanf("%d",&a[j]);
		for(int ok=0,j=1;j<=k;j++){
			if(ok) ds[a[j]]=min(ds[a[j]],c);
			else if(a[j]==s) ok=1;
		}
		for(int ok=0,j=k;j>=1;j--){
			if(ok) dt[a[j]]=min(dt[a[j]],c);
			else if(a[j]==t) ok=1;
		}
		for(int ok=0,j=1;j<=k;j++){
			if(ok==0&&a[j]==s) ok=1;
			if(ok==1&&a[j]==t){
				ans=min(ans,c);
				break;
			}
		}
	}
	for(int i=10000;i;i--)
	    ans=min(ans,ds[i]+dt[i]);
	if(ans==inf) puts("-1");
	else printf("%d\n",ans);
	return 0;
}