记录编号	204681	评测结果	AAAWTTTTTT
题目名称	[SYOI 2015] Asm.Def的打击序列	最终得分	30
用户昵称	WAHT	是否通过	未通过
代码语言	C++	运行时间	24.002 s
提交时间	2015-11-04 15:55:03	内存使用	0.66 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<cstdlib>
using namespace std;


int q[300],map[300][300],vis[300];
int n,m,c;
int ans,len,Ans;
int f[300];

void dijkstra()
{
	int num=0;
	//for(int i=1;i<=len;i++) cout<<q[i]<<' ';
	for(int i=2;i<=len;i++)
	{	
		int tn=q[i-1],to=q[i];
		num+=min(map[tn][to],c);
	}
	num+=min(map[q[len]][q[1]],c);//cout<<num<<' '<<endl;
	ans=min(ans,num);
}
void lian(int s)
{
	memset(vis,0,sizeof(vis));
	int head=0,tail=1;
	vis[s]=1;
	q[1]=s;
	while(head++<tail)
	{
		int tn=q[head];
		for(int i=1;i<=n;i++)
			if(!vis[i]&&map[tn][i]<11000) vis[i]=1,q[++tail]=i,f[i]=1;
	}
	int tail2=1;
	head=0;
	while(head++<tail2)
	{
		int tn=q[head];
		for(int i=1;i<=n;i++)
			if(!vis[i]&&map[i][tn]<11000) vis[i]=1,q[++tail]=i,f[i]=1;
	}
	len=tail+tail2-1;
}
void dfs(int x)
{
	if(x==len+1)
	{
		dijkstra();
	}
	for(int i=1;i<=n;i++)
		if(vis[i])
		{	
			vis[i]=0,q[x]=i;
			dfs(x+1);
			vis[i]=1;
		}
}

void init()
{
	cin>>n>>m>>c;
	memset(map,10,sizeof(map));
	for(int i=1;i<=m;i++)
	{	
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		map[a][b]=min(map[a][b],c);
	}
	for(int i=1;i<=n;i++)
	{
		if(!f[i])
		{
			lian(i);
			ans=map[0][0];
			dfs(1);
			Ans+=ans;
		}
	}

}

int main()
{
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	init();
	cout<<Ans<<endl;
	return 0;
}