记录编号	359267	评测结果	AAAAAAAAAA
题目名称	[USACO Jan15] 牛的路线2	最终得分	100
用户昵称	Arrow	是否通过	通过
代码语言	C++	运行时间	0.009 s
提交时间	2016-12-21 21:04:48	内存使用	0.35 MiB

#include<iostream>
#include<cstdio>
#include<vector>
#define INF 999999
using namespace std;
namespace IO{
	char buf[1<<15],*fs,*ft;
	inline char gc(){return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<15,stdin),fs==ft))?0:*fs++;}
	inline int read(){
		int x=0,rev=0,ch=gc();
		while(ch<'0'||ch>'9'){if(ch=='-')rev=1;ch=gc();}
		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=gc();}
		return rev?-x:x;
	}
}using namespace IO;
/*AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA*/
int main()
{
	freopen("cowrouteb.in","r",stdin);
	freopen("cowrouteb.out","w",stdout);
	int a,b,n;
	int cost,num;
	int start[10010]={0},end[10010]={0},step[10010]={0};
	bool flaga=0,flagb=0,flag1=0,flag2=0;
	int posb,maxnow=0,ans=INF;
	int speicy=0;
	a=read();b=read();n=read();
	for(int i=1;i<=10010;i++)
	{
		start[i]=end[i]=INF;
	}
	for(int i=1;i<=n;i++)
	{
		cost=read();
		num=read();
		for(int j=1;j<=num;j++)
		{
			int now=read();
			if(now>maxnow)
				maxnow=now;
			if(flaga)
			{
				if(cost<start[now])
					start[now]=cost;
			}
			if(now==a)
			{
				flaga=1;
				flag1=1;
				if(!flagb)
					speicy=1;
			}
			step[j]=now;
			if(now==b)
			{
				if(speicy==1)
					speicy=2;
				flagb=1;
				posb=j;
				flag2=1;
			}
			if(speicy==2)
				if(ans>cost)
					ans=cost;
		}
		if(flagb)
		{
			for(int j=posb-1;j>=1;j--)
			{
				if(end[step[j]]>cost)
					end[step[j]]=cost;
			}
		}
		flaga=0;flagb=0;speicy=0;
	}
	if(!(flag1&&flag2))
	{
		printf("-1\n");
		return 0;
	}
	for(int i=1;i<=maxnow;i++)
	{
		if(end[i]+start[i]<ans)
			ans=end[i]+start[i];
	}
	printf("%d\n",ans);
return 0;
}