提交记录 27326


用户 题目 状态 得分 用时 内存 语言 代码长度
wdnmdwrnmmp noip17e. 【NOIP2017】宝藏 Accepted 100 1.196 ms 40 KB C++ 1.21 KB
提交时间 评测时间
2024-11-09 21:03:23 2024-11-09 21:03:28
#include<bits/stdc++.h>
using namespace std;
const int inf=2e9;
int n,m;
int c[20][20],to[20][20],num[20];
int p,ans=inf; 
int tmp=0; 
int tot,cnt,vis[20],di[20];
inline bool cmp(int a,int b)
{
	return c[p][a]<c[p][b];
}
inline void dfs(int st,int sti)
{
	for(int i=st;i<=cnt;i++)
	{
		int si=vis[i];
		if(tot+tmp*di[si]>=ans)
		{
			return;
		}
		for(int j=sti;j<=num[si];j++)
		{
			int sj=to[si][j];
			if(!di[sj])
			{
				cnt++;
				vis[cnt]=sj;
				tmp-=c[sj][to[sj][1]];
				tot+=di[si]*c[si][sj];
				di[sj]=di[si]+1;
				dfs(i,j+1);
				tot-=di[si]*c[si][sj];
				di[sj]=0;
				tmp+=c[sj][to[sj][1]];
				cnt--;
			}
		}
		sti=1;
	}
	if(cnt==n)
	{
		ans=min(ans,tot);
		return;
	}
}
int main()
{
	cin>>n>>m;
	for(int i=0;i<20;i++)
	{
		for(int j=0;j<20;j++)
		{
			c[i][j]=inf;
		}
	}
	for(int i=1;i<=m;i++)
	{
		int u,v,w;
		cin>>u>>v>>w;
		if(c[u][v]<w) continue;
		if(c[u][v]==inf)
		{
			to[u][++num[u]]=v,to[v][++num[v]]=u;
		}
		c[u][v]=c[v][u]=w;
	}
	for(int i=1;i<=n;i++)
	{
		p=i;
		sort(to[i]+1,to[i]+num[i]+1,cmp);
		tmp+=c[i][to[i][1]];
	}
	//cout<<tmp;
	for(int i=1;i<=n;i++)
	{
		tot=0,cnt=1;
		vis[1]=i;
		tmp-=c[i][to[i][1]];
		di[i]=1;
		dfs(1,1);
		di[i]=0;
		tmp+=c[i][to[i][1]];
	}
	cout<<ans;
	return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #143.61 us40 KBAcceptedScore: 5

Testcase #240.71 us40 KBAcceptedScore: 5

Testcase #341.65 us40 KBAcceptedScore: 5

Testcase #440.62 us40 KBAcceptedScore: 5

Testcase #543.89 us40 KBAcceptedScore: 5

Testcase #657.06 us40 KBAcceptedScore: 5

Testcase #743.67 us40 KBAcceptedScore: 5

Testcase #848.87 us40 KBAcceptedScore: 5

Testcase #9239.92 us40 KBAcceptedScore: 5

Testcase #10132.45 us40 KBAcceptedScore: 5

Testcase #1199.79 us40 KBAcceptedScore: 5

Testcase #12105.69 us40 KBAcceptedScore: 5

Testcase #13111.77 us40 KBAcceptedScore: 5

Testcase #14146.3 us40 KBAcceptedScore: 5

Testcase #15478.31 us40 KBAcceptedScore: 5

Testcase #16605.68 us40 KBAcceptedScore: 5

Testcase #17432.05 us40 KBAcceptedScore: 5

Testcase #18470.19 us40 KBAcceptedScore: 5

Testcase #191.196 ms40 KBAcceptedScore: 5

Testcase #20818.61 us40 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2024-12-04 10:36:44 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用 | 捐赠