|
问题分析
我们去考虑如何设计一个状态，才能满足无后效性和最优子结构呢？ 如果我们从一维去想，用
dp[v]
d
p
[
v
]
表示终点为
v
v
时花费的最小时间是多少，那么明显是不够的，因为它无法保证你是否访问节点的时候会重复，然鹅题目要求恰好每一个节点只访问一次。所以，我们去加一维集合状态去约束它。用dp[S][v]dp[S][v]来表示恰好已经无重复访问节点集合
S
S
并且终点为vv时所花费的最小时间，这样我们就可以满足题意了。 转移方程也显然易见
dp[S][v]=min{dp[s′][u]+e[u][v]}
d
p
[
S
]
[
v
]
=
m
i
n
{
d
p
[
s
′
]
[
u
]
+
e
[
u
]
[
v
]
}
此时
v∈S,s′=S–v,u∈s′
v
∈
S
,
s
′
=
S
–
v
,
u
∈
s
′
#include
using namespace std;
int n,e[20][20],dp[1 u & 1)) //如果u属于s集合
res = min(res, rec(s - (1 >n;
for(int i = 0; i < n; ++i){
for(int j = 0; j < n; ++j){
cin>>e[i][j];
}
}
/*初始到达目标并且访问完所有集合所需代价无穷大*/
for(int i = 1; i < 1 |