/ Randle /

记录详情

Accepted


  
# 状态 耗时 内存占用
#1 Accepted 16ms 32.699 MiB
#2 Accepted 17ms 32.703 MiB
#3 Accepted 15ms 32.691 MiB
#4 Accepted 19ms 32.727 MiB
#5 Accepted 21ms 32.727 MiB
#6 Accepted 17ms 32.699 MiB
#7 Accepted 17ms 32.637 MiB
#8 Accepted 29ms 32.73 MiB
#9 Accepted 20ms 32.73 MiB
#10 Accepted 18ms 32.699 MiB

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxint 2147483647

using namespace std;
typedef long long llg;

int n,dp[500001][17];
int d[17][17];

int getint(){
	int w=0,q=0;
	char c=getchar();
	while((c>'9'||c<'0')&&c!='-') c=getchar();
	if(c=='-') q=1,c=getchar();
	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();
	return q?-w:w;
}

int main(){
	n=getint();n++;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
		        d[i][j]=getint();
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				if(i!=j && i!=k && j!=k)
					if(d[i][k]+d[k][j]<d[i][j])
						d[i][j]=d[i][k]+d[k][j];
	memset(dp,0x7f,sizeof(dp));
	dp[0][1]=0;
	int i,j,l;
	for(i=1;i<(1<<n);i++)
		for(j=1;j<=n;j++)
			for(l=1;l<=n;l++) if(j!=l && (i&(1<<(l-1))) && dp[i-(1<<(l-1))][l]+d[l][j]>=0)
				dp[i][j]=min(dp[i][j],dp[i-(1<<(l-1))][l]+d[l][j]);
	printf("%d",dp[(1<<n)-1][1]);
	return 0;
}

信息

递交者
类型
递交
题目
送外卖
题目数据
下载
语言
C++
递交时间
2019-06-13 20:41:45
评测时间
2019-06-13 20:41:45
评测机
分数
100
总耗时
194ms
峰值内存
32.73 MiB