比赛 |
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;
}