提交记录 11035


用户 题目 状态 得分 用时 内存 语言 代码长度
flwfdd noip17e. 【NOIP2017】宝藏 Accepted 100 674.244 ms 3364 KB C++ 1.42 KB
提交时间 评测时间
2019-10-22 22:51:54 2020-08-01 02:37:59
#include<bits/stdc++.h>
using namespace std;

int n,m,val[12][12],ans,bestn[12],best,ii;
int to[12][13];//数量,12*边。 

struct node{
	int w,dp[12];//dp[i][j]点i深度为j 
}f[65536];

void find(int k)
{
	if(k==(1<<n)-1)
	{
		//printf("#%d&%d\n",f[k].w,best);
		ans=min(f[k].w,ans);
		return;
	}
	if(f[k].w+best>=ans)return;
	int mk,j;
	for(int i=0;i<n;i++)
	{
		if(!(k&(1<<i)))continue;
		if(f[k].w+best*f[k].dp[i]>=ans)continue;
		for(int jj=1;jj<=to[i][0];jj++)
		{
			j=to[i][jj];
			if(k&(1<<j))continue;
			mk=k|(1<<j);
			memcpy(f[mk].dp,f[k].dp,sizeof(f[k].dp));
			f[mk].w=f[k].w+f[k].dp[i]*val[i][j];
			f[mk].dp[j]=f[k].dp[i]+1;
			best-=bestn[j];
			find(mk);
			best+=bestn[j]; 
		}
	}
}

void solve(int rt)
{
	memset(f,0,sizeof(f));
	f[1<<rt].w=0;
	f[1<<rt].dp[rt]=1;
	
	best-=bestn[rt];
	find(1<<rt);
	best+=bestn[rt]; 
}

bool cmp(int a,int b)
{
	return val[ii][a]<val[ii][b];
}

int main()
{
	freopen("test.in","r",stdin);
	int m1,m2,m3;
	cin>>n>>m;
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)val[i][j]=0x7fffffff;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&m1,&m2,&m3);
		m1--;m2--;
		val[m1][m2]=min(val[m1][m2],m3);
		val[m2][m1]=min(val[m2][m1],m3);	
	}
	for(int i=0;i<n;i++)
	{
		m1=0;
		for(int j=0;j<n;j++)
		{
			if(val[i][j]==0x7fffffff)continue;
			to[i][++m1]=j;
		}
		to[i][0]=m1;
		ii=i;
		sort(to[i]+1,to[i]+1+m1,cmp);
		bestn[i]=val[i][to[i][1]];
		best+=bestn[i];
	}
	ans=0x7fffffff;
	for(int i=0;i<n;i++)solve(i);
	cout<<ans;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #1305.08 us3 MB + 292 KBAcceptedScore: 5

Testcase #2589.44 us3 MB + 292 KBAcceptedScore: 5

Testcase #3804.09 us3 MB + 292 KBAcceptedScore: 5

Testcase #4803.51 us3 MB + 292 KBAcceptedScore: 5

Testcase #5806 us3 MB + 292 KBAcceptedScore: 5

Testcase #6722.1 us3 MB + 292 KBAcceptedScore: 5

Testcase #7651.45 us3 MB + 292 KBAcceptedScore: 5

Testcase #8720.51 us3 MB + 292 KBAcceptedScore: 5

Testcase #9633.66 us3 MB + 292 KBAcceptedScore: 5

Testcase #10693.42 us3 MB + 292 KBAcceptedScore: 5

Testcase #11784.77 us3 MB + 292 KBAcceptedScore: 5

Testcase #12777.92 us3 MB + 292 KBAcceptedScore: 5

Testcase #131.021 ms3 MB + 292 KBAcceptedScore: 5

Testcase #141.04 ms3 MB + 292 KBAcceptedScore: 5

Testcase #1572.221 ms3 MB + 292 KBAcceptedScore: 5

Testcase #1656.941 ms3 MB + 292 KBAcceptedScore: 5

Testcase #17178.327 ms3 MB + 292 KBAcceptedScore: 5

Testcase #18117.379 ms3 MB + 292 KBAcceptedScore: 5

Testcase #19674.244 ms3 MB + 292 KBAcceptedScore: 5

Testcase #20574.772 ms3 MB + 292 KBAcceptedScore: 5


Judge Duck Online | 评测鸭在线
Server Time: 2020-10-29 19:53:27 | Loaded in 1 ms | Server Status
个人娱乐项目,仅供学习交流使用