| 比赛 |
“Asm.Def战记之拉格朗日点”杯 |
评测结果 |
RRRRRRRRRR |
| 题目名称 |
Asm.Def的打击序列 |
最终得分 |
0 |
| 用户昵称 |
fengchenxue |
运行时间 |
0.005 s |
| 代码语言 |
C++ |
内存使用 |
0.32 MiB |
| 提交时间 |
2015-11-04 11:53:49 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<cstring>
#include<string>
#include<cstdlib>
using namespace std;
int n,m,c,ans;
bool use[260];
struct str{
vector<int> son;
vector<int> w;
}f[260];
void fun(int x,int y)
{
int ok=0,p=0;
if(f[x].son.empty()==1)
{
if(use[x]==0)
{
use[x]=1;
for(int i=1;i<=n;i++)
{
if(use[i]==0)
{
fun(i,y+c);
}
}
use[x]=0;
return;
}
for(int i=1;i<=n;i++)
{
if(use[i]==0)
{
p=1;
fun(i,y);
}
}
if(p==0)
{
ans=min(ans,y);
// cout<<use[1]<<use[2]<<use[3]<<use[4]<<use[5]<<use[6]<<endl;
// cout<<x<<" "<<y<<endl;
}
return;
}
for(int i=0;i<f[x].son.size();i++)
{
if(use[f[x].son[i]]==0)
{
ok=1;
use[f[x].son[i]]=1;
fun(f[x].son[i],y+f[x].w[i]);
use[f[x].son[i]]=0;
}
}
// cout<<x<<" "<<ok<<endl;
if(ok==0)
{
// cout<<x<<" "<<use[x]<<endl;
if(use[x]==0)
{
use[x]=1;
for(int i=1;i<=n;i++)
{
if(use[i]==0)
{
fun(i,y+c);
}
}
use[x]=0;
return;
}
for(int i=1;i<=n;i++)
{
if(use[i]==0)
{
p=1;
fun(i,y);
}
}
if(p==0)
{
// cout<<use[1]<<use[2]<<use[3]<<use[4]<<use[5]<<use[6]<<endl;
ans=min(ans,y);
}
return;
}
}
int main()
{
// freopen("asm_lis.in","r",stdin);
// freopen("asm_lis.out","w",stdout);
int k1,k2,k3;
cin>>n>>m>>c;
ans=c*n;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&k1,&k2,&k3);
f[k1].son.push_back(k2);
f[k1].w.push_back(k3);
}
for(int i=1;i<=n;i++)
{
fun(i,0);
}
cout<<ans;
return 0;
}