记录编号	204423	评测结果	AAWWEEEEEE
题目名称	[SYOI 2015] Asm.Def的打击序列	最终得分	20
用户昵称	momo123	是否通过	未通过
代码语言	C++	运行时间	0.449 s
提交时间	2015-11-04 12:16:19	内存使用	0.31 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<map>
#include<queue>
#include<vector>
#include<stack>
using namespace std;
int n,d[10][10],minn,m,c,ans=100000000;
int main()
{
	freopen("asm_lis.in","r",stdin);
	freopen("asm_lis.out","w",stdout);
	cin>>n>>m>>c;
	for(int i=1;i<=n;i++)
	   for(int j=1;j<=n;j++)
	      d[i][j]=1000000;
	if(n==2)
	{
		for(int i=1;i<=m;i++)
		{
			int u,v,s;
			cin>>u>>v>>s;
			d[u][v]=min(d[u][v],s);
		}
		ans=min(ans,d[1][2]+c);
		ans=min(ans,d[2][1]+c);
		ans=min(ans,2*c);
		ans=min(ans,d[1][2]+d[2][1]);
		cout<<ans;
	}
	if(n==3)
	{
		for(int i=1;i<=m;i++)
		{
			int u,v,s;
			cin>>u>>v>>s;
			d[u][v]=min(d[u][v],s);
		}
		ans=min(ans,d[1][2]+d[2][3]+c);
		ans=min(ans,d[1][2]+d[2][1]+c);
		ans=min(ans,d[3][2]+d[2][3]+c);
		ans=min(ans,d[1][3]+d[3][1]+c);
		ans=min(ans,d[3][2]+d[2][1]+c);
		ans=min(ans,d[1][3]+d[3][2]+c);
		ans=min(ans,d[2][3]+d[3][1]+c);
		ans=min(ans,d[2][1]+d[1][3]+c);
		ans=min(ans,d[3][1]+d[1][2]+c);
		ans=min(ans,d[2][1]+2*c);
		ans=min(ans,d[1][2]+2*c);
		ans=min(ans,d[1][3]+2*c);
		ans=min(ans,d[3][1]+2*c);
		ans=min(ans,d[2][3]+2*c);
		ans=min(ans,d[3][2]+2*c);
		ans=min(ans,3*c);
		ans=min(ans,d[1][2]+d[2][3]+d[3][1]);
		ans=min(ans,d[2][1]+d[1][3]+d[3][2]);
		cout<<ans<<endl;
	}
	if(n==4)
	{
		for(int i=1;i<=m;i++)
		{
			int u,v,s;
			cin>>u>>v>>s;
			d[u][v]=min(d[u][v],s);
		}
		ans=min(ans,d[1][2]+d[2][3]+d[3][4]+c);
		ans=min(ans,d[1][2]+d[2][4]+d[4][3]+c);
		ans=min(ans,d[1][3]+d[3][2]+d[2][4]+c);
		ans=min(ans,d[1][4]+d[4][2]+d[2][3]+c);
		ans=min(ans,d[1][4]+d[4][3]+d[3][2]+c);	
		ans=min(ans,d[1][2]+d[2][4]+d[4][3]+c);
		ans=min(ans,d[1][3]+d[3][4]+d[4][2]+c);
		ans=min(ans,d[2][3]+d[3][1]+d[1][4]+c);
		ans=min(ans,d[2][3]+d[3][4]+d[4][1]+c);
		ans=min(ans,d[2][1]+d[1][3]+d[3][4]+c);
		ans=min(ans,d[2][1]+d[1][4]+d[4][3]+c);
		ans=min(ans,d[2][4]+d[4][1]+d[1][3]+c);
		ans=min(ans,d[2][4]+d[4][3]+d[3][1]+c);
		ans=min(ans,d[3][1]+d[1][2]+d[2][4]+c);
		ans=min(ans,d[3][1]+d[1][4]+d[4][2]+c);
		ans=min(ans,d[3][2]+d[2][4]+d[4][1]+c);
		ans=min(ans,d[3][2]+d[2][1]+d[1][4]+c);
		ans=min(ans,d[3][4]+d[4][1]+d[1][2]+c);
	    ans=min(ans,d[3][4]+d[4][2]+d[2][1]+c);
	    //-------------------------------------
	    ans=min(ans,d[1][2]+d[2][3]+2*c);
		ans=min(ans,d[3][2]+d[2][1]+2*c);
		ans=min(ans,d[1][3]+d[3][2]+2*c);
		ans=min(ans,d[2][3]+d[3][1]+2*c);
		ans=min(ans,d[2][1]+d[1][3]+2*c);
		ans=min(ans,d[3][1]+d[1][2]+2*c);
		ans=min(ans,d[1][2]+d[2][4]+2*c);
		ans=min(ans,d[4][2]+d[2][1]+2*c);
		ans=min(ans,d[1][4]+d[4][2]+2*c);
		ans=min(ans,d[2][4]+d[4][1]+2*c);
		ans=min(ans,d[2][1]+d[1][4]+2*c);
		ans=min(ans,d[4][1]+d[1][2]+2*c);
		ans=min(ans,d[4][2]+d[2][3]+2*c);
		ans=min(ans,d[3][2]+d[2][4]+2*c);
		ans=min(ans,d[4][3]+d[3][2]+2*c);
		ans=min(ans,d[2][3]+d[3][4]+2*c);
		ans=min(ans,d[2][4]+d[4][3]+2*c);
		ans=min(ans,d[3][4]+d[4][2]+2*c);
		ans=min(ans,d[1][4]+d[4][3]+2*c);
		ans=min(ans,d[3][4]+d[4][1]+2*c);
		ans=min(ans,d[1][3]+d[3][4]+2*c);
		ans=min(ans,d[4][3]+d[3][1]+2*c);
		ans=min(ans,d[4][1]+d[1][3]+2*c);
		ans=min(ans,d[3][1]+d[1][4]+2*c);
		//-----------------------------
		ans=min(ans,d[1][4]+3*c);
		ans=min(ans,d[1][2]+3*c);
		ans=min(ans,d[1][3]+3*c);
		ans=min(ans,d[3][1]+3*c);
		ans=min(ans,d[3][4]+3*c);
		ans=min(ans,d[3][2]+3*c);
		ans=min(ans,d[2][1]+3*c);
		ans=min(ans,d[2][4]+3*c);
		ans=min(ans,d[2][3]+3*c);
		ans=min(ans,d[4][1]+3*c);
		ans=min(ans,d[4][2]+3*c);
		ans=min(ans,d[4][3]+3*c);
		ans=min(ans,4*c);
		ans=min(ans,d[1][2]+d[2][3]+d[3][4]+d[4][1]);
		ans=min(ans,d[4][3]+d[3][2]+d[2][1]+d[1][4]);
		//--------------------------------
		ans=min(ans,d[1][2]+d[2][1]+2*c);
		ans=min(ans,d[3][2]+d[2][3]+2*c);
		ans=min(ans,d[1][3]+d[3][1]+2*c);
		ans=min(ans,d[4][1]+d[1][4]+2*c);
		ans=min(ans,d[2][4]+d[4][2]+2*c);
		ans=min(ans,d[3][4]+d[4][3]+2*c);
		//--------------------------------
		cout<<ans<<endl;
	}
}