提交记录 12799


用户 题目 状态 得分 用时 内存 语言 代码长度
winlere noip17e. 【NOIP2017】宝藏 Accepted 100 307.101 ms 680 KB C++11 1.57 KB
提交时间 评测时间
2020-06-03 20:13:42 2020-08-01 02:58:55
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>

using namespace std;  typedef long long ll;
inline int qr(){
      register int ret=0,f=0;
      register char c=getchar();
      while(!isdigit(c))f|=c==45,c=getchar();
      while(isdigit(c)) ret=ret*10+c-48,c=getchar();
      return f?-ret:ret;
}

const int maxn=13;
const int inf=0x3f3f3f3f;
int e[maxn][maxn];
int dp[maxn][1<<maxn];
int dis[maxn][1<<maxn];
int n,m,rt;
int cnt=0;

int main(){
      memset(e,0x3f,sizeof e);
      memset(dp,0x3f,sizeof dp);
      n=qr(); m=qr();
      for(int t=1,t1,t2;t<=m;++t)
	    t1=qr(),t2=qr(),e[t1][t2]=e[t2][t1]=min(e[t1][t2],qr());
      const int K=(1<<n)-1;
      for(int t=0;t<=K;++t)
	    for(int g=1;g<=n;++g){
		  if(t<<1>>g&1) continue;
		  int f=inf;
		  for(int k=1;k<=n;++k)
			if(t<<1>>k&1) f=min(f,e[g][k]);
		  dis[g][t]=f;
	    }
      int ans=inf;
      for(int rt=1;rt<=n;++rt){
	    memset(dp,0x3f,sizeof dp);
	    dp[1][1<<rt>>1]=0;
	    for(int t=2;t<=n;++t){
		  for(int i=1;i<=K;++i){
			dp[t][i]=dp[t-1][i];
			for(int l=i;l;--l&=i){
			      int c=l^i,ret=0;
			      if(dp[t-1][c]>=dp[t][i])continue;
			      bool f=0;
			      for(int g=1;g<=n;++g)
				    if(l<<1>>g&1){
					  if(dis[g][c]>=inf){ret=inf; break;}
					  else ret+=dis[g][c];
					  if(dp[t-1][c]+(t-1)*ret>=dp[t][i]) {f=1;break;}
				    }
			      if(f)continue;
			      dp[t][i]=min((ll)dp[t][i],dp[t-1][c]+(t-1ll)*ret);
			}
		  }
		  ans=min(ans,dp[t][K]);
	    }
	    ans=min(ans,dp[1][K]);
      }
      printf("%d\n",ans);
      return 0;
}

CompilationN/AN/ACompile OKScore: N/A

Testcase #177.69 us460 KBAcceptedScore: 5

Testcase #2135.83 us476 KBAcceptedScore: 5

Testcase #3631.22 us488 KBAcceptedScore: 5

Testcase #4666.57 us488 KBAcceptedScore: 5

Testcase #51.153 ms488 KBAcceptedScore: 5

Testcase #6372.71 us484 KBAcceptedScore: 5

Testcase #7189.86 us480 KBAcceptedScore: 5

Testcase #8378.16 us484 KBAcceptedScore: 5

Testcase #9150.55 us476 KBAcceptedScore: 5

Testcase #10214.81 us480 KBAcceptedScore: 5

Testcase #11481.9 us484 KBAcceptedScore: 5

Testcase #12455.09 us484 KBAcceptedScore: 5

Testcase #131.601 ms488 KBAcceptedScore: 5

Testcase #141.369 ms488 KBAcceptedScore: 5

Testcase #1573.913 ms580 KBAcceptedScore: 5

Testcase #1675.216 ms580 KBAcceptedScore: 5

Testcase #17307.101 ms680 KBAcceptedScore: 5

Testcase #18240.156 ms680 KBAcceptedScore: 5

Testcase #19265.866 ms680 KBAcceptedScore: 5

Testcase #20294.882 ms680 KBAcceptedScore: 5


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