比赛 20150408 评测结果 RRRRRRRRRRRR
题目名称 牛的路线 最终得分 0
用户昵称 slyrabbit 运行时间 0.003 s
代码语言 C++ 内存使用 0.43 MiB
提交时间 2015-04-08 21:06:18
显示代码纯文本
#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;
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;
	}
	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;
		}
		work(next_city,i,a[next_city].city[i].line);
		if(t)
		{
			ans-=a[next_city].city[i].cost;
		    b[line]=0;
		}
	}
}
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;
	    work(A,i,a[A].city[i].line);
		ans-=a[A].city[i].cost;
	}
	if(min_cost!=10000000)
	    cout<<min_cost;
	else
		cout<<-1;
	return 0;
}