dd爱探险

NC221821. dd爱探险

描述

星际中有 $n$ 个空间站，任意两个空间站间可以相互跳跃，由空间站 $x$ 跳跃到空间站 $y$ 所需要的代价为 $P[x][y]$ ,注意不保证 $p[x][y]=p[y][x]$ ， $dd$ 可以任意选择出发的空间站，并通过恰好 $n-1$ 次跳跃把所有空间站跳完，并且 $dd$ 必须选择 $2$ 次跳跃，其中一次跳跃中进行重力加速，另一次跳跃中进行反重力加速，重力加速会导致当前跳跃代价变为 $0$ ，反重力加速会导致当前跳跃代价翻倍(乘 $2$ )，问跳完所有空间站所需要最小代价

输入描述

第一行一个数n(3≤n≤16)
接下来n行每行n个数，第x行第y个数表示p[x][y](0≤p[x][y]≤100000)

输出描述

一个数,表示最小代价

示例1

输入:

输出:

说明:

1->2重力加速
2->3反重力加速
代价0+1*2=2

上次编辑到这里，代码来自缓存点击恢复默认模板

C++ 解法, 执行用时: 473ms, 内存消耗: 16848K, 提交时间: 2021-05-28 21:01:54

#include<bits/stdc++.h>
using namespace std;
const int N=16;
int dp[N][4][1<<N];
int p[N][N];
int n;
int dfs(int u,int b,int st){
	if(b==0&&(st==(1<<n)-1))return 0;
	if(dp[u][b][st]!=-1)return dp[u][b][st];
	int res=1e9;
	for(int v=0;v<n;v++){
		if(st&(1<<v))continue;
		int nst=st|(1<<v);
		if(b&1)res=min(res,dfs(v,b&(~1),nst)+2*p[u][v]);
		if(b&2)res=min(res,dfs(v,b&(~2),nst));
		res=min(res,dfs(v,b,nst)+p[u][v]);
	}
	return dp[u][b][st]=res;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			cin>>p[i][j];
		}
	}
	memset(dp,-1,sizeof dp);
	int ans=1e9;
	for(int i=0;i<n;i++){
		ans=min(ans,dfs(i,3,1<<i));
	}
	cout<<ans;
}