记录编号	157834	评测结果	AAAAAATTTT
题目名称	[USACO Jan15] 牛的路线2	最终得分	60
用户昵称	slyrabbit	是否通过	未通过
代码语言	C++	运行时间	4.010 s
提交时间	2015-04-10 20:07:57	内存使用	0.43 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
class student
{
public:
	int point;
	int line;
	int cost;
};
class CITY
{
public:
	vector<student>city;
}a[10005];
int A,B,n,Acity_max=0,ans=0,min_cost=10000000,TIME=0;
bool b[505]={0};
void init()
{
	cin>>A>>B>>n;
	for(int i=1;i<=n;i++)
	{
		int cost,num,temp1,temp2;
		cin>>cost>>num>>temp1;
		for(int j=1;j<num;j++)
		{
			cin>>temp2;
			student temp;
			temp.point=temp2;
			temp.line=i;
			temp.cost=cost;
			a[temp1].city.push_back(temp);
			if(temp1==A)
				Acity_max++;
			temp1=temp2;
		}
	}
}
void work(int l,int r,int line)
{
	int next_city=a[l].city[r].point;
	if(next_city==B)
	{
		min_cost=min(min_cost,ans);
		return;
	}
	if(TIME>2)
		return;
	for(int i=0;i<a[next_city].city.size();i++)
	{
		bool t=0;
		if(b[a[next_city].city[i].line]==1)
			continue;
		if(a[next_city].city[i].line!=line)
		{
			ans+=a[next_city].city[i].cost;
		    b[line]=1;
			t=1;
			TIME+=1;
		}
		work(next_city,i,a[next_city].city[i].line);
		if(t)
		{
			ans-=a[next_city].city[i].cost;
		    b[line]=0;
			TIME-=1;
		}
	}
}
int main()
{
	freopen("cowrouteb.in","r",stdin);
	freopen("cowrouteb.out","w",stdout);
	init();
	for(int i=0;i<Acity_max;i++)
	{
		ans+=a[A].city[i].cost;
		TIME+=1;
	    work(A,i,a[A].city[i].line);
		TIME-=1;
		ans-=a[A].city[i].cost;
	}
	if(min_cost!=10000000)
	    cout<<min_cost;
	else
		cout<<-1;
	return 0;
}