厄神降临之路

Python3 解法, 执行用时: 44ms, 内存消耗: 4740K, 提交时间: 2023-05-19 20:49:07

n = int(input())
arr = input().strip().split()
from collections import defaultdict
p = {}
for i,num in enumerate(arr):
    p[1<<i] = int(num)

    
road = defaultdict(list)
line = {}
for i in range(n):
    arr = input().strip().split()
    for j,num in enumerate(arr):
        num = int(num)
        if not num:
            continue
            
        road[1<<i].append((1<<j,num))
        line[(1<<i,1<<j)] = num
#         road[1<<j].append((1<<i,num))


visited = set()
global res
res = float("inf")
def dfs(start,cur,level,t1,t2):
    global res
    
    if t1 * t2 >= res:
        return
    
    if level > 2 and (start,cur) in line: 
        tmp = t1 * (t2+line[(start,cur)])
        if tmp < res:
            res = tmp
        return
        
    for nxt,c in road[cur]:
        if nxt not in visited:
            visited.add(nxt)
            dfs(start,nxt,level+1,t1+p[nxt],t2+c)
            visited.remove(nxt)
    

for start in range(n):
    src = 1 << start
    visited.add(src)
    dfs(src,src,1,p[src],0)
    visited.remove(src)

if res != float("inf"):
    print(res)
else:
    print(-1)

C++(g++ 7.5.0) 解法, 执行用时: 1260ms, 内存消耗: 98944K, 提交时间: 2023-05-19 20:46:38

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
const int N=22;
int a[N],g[1<<N],dp[1<<N][N],s[1<<N];
int b[N][N];
int n;
int main(){
	scanf("%d",&n);
	for (int i=0;i<n;i++) scanf("%d",&a[i]);
	for (int i=0;i<(1<<n);i++) g[i]=INF;
	for (int i=0;i<n;i++) 
		for (int j=0;j<n;j++) scanf("%d",&b[i][j]);
	for (int k=0;k<n;k++){
		for (int i=0;i<(1<<n);i++) if ((i&(-i))==(1<<k)){
			if ((i==(1<<k))) {
			dp[i][k]=0;
			if (b[k][k]) g[i]=min(g[i],b[k][k]);
			continue;
			}
			int t=(i^(1<<k));
			t^=(t&(-t));
			for (int j=k+1;j<n;j++) if ((i>>j)&1){
				dp[i][j]=INF;
				for (int p=k+(t>0?1:0);p<n;p++) if (((i>>p)&1)&&b[p][j]&&p!=j&&dp[i^(1<<j)][p]!=INF){
					dp[i][j]=min(dp[i][j],dp[i^(1<<j)][p]+b[p][j]);
				}
				if (t&&dp[i][j]!=INF&&b[k][j]) {
				g[i]=min(g[i],dp[i][j]+b[k][j]);
				}
			}
		}
	}
	long long ans=1e18;
	for (int i=0;i<(1<<n);i++){
		if (i) s[i]=s[i^(i&(-i))]+a[(int)log2(i&(-i))];
		if (g[i]!=INF&&ans>1ll*s[i]*g[i]) {
		ans=min(ans,1ll*s[i]*g[i]);
		}
	}
	if (ans==1e18) puts("-1"); else printf("%lld\n",ans);
}

C++(clang++ 11.0.1) 解法, 执行用时: 4ms, 内存消耗: 472K, 提交时间: 2023-05-19 21:49:19

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll t,n,m,ans,sum,mi=1e9,k,x,y,r,dp[50][50],z=1e17,a[50],p[50][50];
void dfs(ll ans,ll sum,int x,int y)
{
	if(ans*sum>z)
	{
		return;
	}
	if(x==y)
	{
		z=min(z,ans*sum);
		return;
	}
	for(int i=1;i<=n;i++)
	{
		if(dp[x][i]&&!p[x][i])
		{
			p[x][i]=p[i][x]=1;
			dfs(ans+a[i],sum+dp[x][i],i,y);
			p[x][i]=p[i][x]=0;
		}
	}
}
void sovel()
{
	cin>>n;
    for(int i=1;i<=n;i++)
    {
    	cin>>a[i];
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			cin>>dp[i][j];
		}
	}
	for(int i=1;i<=n;i++)
	{
		p[i][i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(i!=j&&dp[i][j])
			{
				p[j][i]=p[i][j]=1;
				dfs(a[j],dp[i][j],j,i);
				p[j][i]=p[i][j]=0;
			}
		}
	}
	if(z==1e17)
	{
		z=-1;
	}
	cout<<z;
}
int main() {
	t=1;
	while(t--)
	{
		sovel();
	 } 
	
}

详情