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

#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
ifstream in("cowrouteb.in");
ofstream out("cowrouteb.out");
const int S=501;
int start,end,best=9999999;
int n,w[S]={0};
vector<int> f[S],l[S],r[S],p;
bool t[S]={0};
int main()
{
	int i,j,k,q;
    int a=0,b=0,dis=9999999,count=0;
	in>>start>>end;
	in>>n;
	for(i=1;i<=n;i++)
	{
		in>>w[i]>>q;
		//out<<w<<' '<<q<<endl;
		a=b=0;
		for(j=1;j<=q;j++)
		{
			in>>k;
			f[i].push_back(k);
			//out<<k<<' ';
			if(k==start)a=j;
			if(k==end)b=j;
			//out<<a<<' '<<b<<endl;
			if(a&&b&&a<b)
			{
				if(w[i]<best)best=w[i];
				//break;
			}
		}
	}
	//out<<best<<endl;
	for(i=1;i<=n;i++)
	{
		a=b=0;
		bool have=1;
		for(j=0;j<f[i].size();j++)
		{
			if(f[i][j]==start)a=j;
			if(f[i][j]==end)b=j;
			if(a&&b&&a<b)
			{
				have=0;
				break;
			}
		}
		//a=b=0;
		//out<<have<<' ';
		if(have)
		{
			//out<<i<<' ';
		for(j=0;j<f[i].size();j++)
		{
			//if(a==b&&a<b)t[i]=1;
			//if(a&&b&&a<b)a=b=0;
			//if(a)l[i].push_back(f[i][j]);
			//if(b)r[i].push_back(f[i][j]);
			if(f[i][j]==start&&j!=f[i].size()-1&&!a)
			{
				a=i;
			}
			if(f[i][j]==end&&j!=0&&!b)b=i;
		}
		if(a)for(j=a;j<f[i].size();j++)l[i].push_back(f[i][j]);
		if(b)for(j=0;j<b;j++)
		{
			r[i].push_back(f[i][j]);
		}
		
		}
	}
	/*for(i=1;i<=n;i++)
	{
		for(j=0;j<r[i].size();j++)
		{
			out<<r[i][j]<<' ';
		}
		out<<endl;
	}*/
	/*for(i=1;i<=n;i++)
	{
		if(l[i].size()!=0)sort(l[i].begin(),l[i].end());
		if(r[i].size()!=0)sort(r[i].begin(),r[i].end());
	}*/
	for(i=1;i<=n;i++)
	{
		if(l[i].size()==0)continue;
		for(j=1;j<=n;j++)
		{
			if(r[j].size()==0)continue;
			//out<<i<<' '<<j<<endl;
			p.clear();
			for(k=0;k<l[i].size();k++)p.push_back(l[i][k]);
			for(k=0;k<r[j].size();k++)p.push_back(r[j][k]);
			sort(p.begin(),p.end());
			//for(k=0;k<p.size();k++)out<<p[k]<<'*';
			//out<<endl;
			//out<<w[i]+w[j]<<' ';
			//out<<endl;
			for(k=0;k<p.size()-1;k++)
			{
				//out<<p[k]<<endl;
				if(p[k]==p[k+1])
				{
					//out<<w[i]<<' '<<w[j]<<endl;
					dis=w[i]+w[j];
					if(dis<best)best=dis;
					break;
				}
			}
		}
	}
	if(start==end)best=0;
	if(best!=9999999)out<<best<<endl;
	else out<<-1<<endl;
	return 0;
}