比赛 20150408 评测结果 AAAEEEEEEE
题目名称 牛的路线2 最终得分 30
用户昵称 KZNS 运行时间 0.533 s
代码语言 C++ 内存使用 0.32 MiB
提交时间 2015-04-08 20:59:42
显示代码纯文本
#include<fstream>
#include<vector>
using namespace std;
int rsq[505]={0};
int a,b,n,mi=500009;
bool mpu[505]={0};
class qwertyuiop{
public:
	int p,r;
}us;
vector<qwertyuiop>mp[505];
void dfs(int dp,int usw){
	if(dp==b){
		int s=0;
		mpu[usw]=1;
		for(int i=1;i<n;i++)
			if(mpu[i])
				s+=rsq[i];
		if(mi>s)mi=s;
		mpu[usw]=0;
		return;
	}
	for(int i=0;i<mp[dp].size();i++){
		if(mp[dp][i].r==usw)
			dfs(mp[dp][i].p,usw);
		else
			if(!mpu[mp[dp][i].r]){
				mpu[usw]=1;
				dfs(mp[dp][i].p,mp[dp][i].r);
				mpu[usw]=0;
			}
	}
}
int main(){
	ifstream fi("cowrouteb.in");
	ofstream fo("cowrouteb.out");
	int y,u;
	fi>>a>>b>>n;
	n++;
	for(int i=1;i<n;i++){
		fi>>rsq[i]>>y>>u;
		us.r=i;
		for(int j=1;j<y;j++){
			fi>>us.p;
			mp[u].push_back(us);
			u=us.p;
		}
	}
	dfs(a,0);
	if(mi==500009)
		fo<<-1<<endl;
	else
		fo<<mi<<endl;
	return 0;
}