| 比赛 |
“Asm.Def战记之拉格朗日点”杯 |
评测结果 |
AAWWEEEEEE |
| 题目名称 |
Asm.Def的打击序列 |
最终得分 |
20 |
| 用户昵称 |
momo123 |
运行时间 |
0.764 s |
| 代码语言 |
C++ |
内存使用 |
0.31 MiB |
| 提交时间 |
2015-11-04 11:49:23 |
显示代码纯文本
#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;
}
}