题意是给你一个图，每个节点最多走两次，求将图联通的最小路径的总长度值。
怎么做？
每个节点最多走两次，那么可以化成“三进制”。
“三进制？三进制电脑怎么表示？”
不说话，看代码
// pow3[i] 代表3^i
int pow3[11];
// inch3[i][j] 代表数字 i 在三进制表示下的第 j 位是几
int inch3[60000][11];
void init()
{
pow3[0]=1;
for(int i=1;i<11;++i)
{
// 递推求幂
pow3[i]=pow3[i-1]*3;
}
for(int i=0;i<pow3[10];++i)
{
// 模拟求三进制
int k=i;
int pos=0;
while(k)
{
inch3[i][pos]=k%3;
k/=3;
pos++;
}
}
}
然后呢？
枚举每种状态，进行动态规划。这 TM 好像 Flyod
for(int i=0;i<pow3[n];++i)
{
bool have_not_visited=0;
for(int j=0;j<n;++j)
{
if(inch3[i][j]==0)
{
have_not_visited=1;
}
if(dp_map[i][j]!=INT_MAX)
{
for(int k=0;k<n;++k)
{
if(mapn[j][k]!=INT_MAX&&inch3[i][k]!=2)
{
dp_map[i+pow3[k]][k]=min(dp_map[i+pow3[k]][k],dp_map[i][j]+mapn[j][k]);
}
}
}
}
然后就 A 了