题解 P4962 【朋也与光玉】
ouuan
2018-11-03 23:05:32
此题按题意搜索 / $dp$ 即可，但如果搜索必须记忆化（说不定有什么神奇的剪枝能过这道题吧...出题人不知道QAQ）。
题解把代码改好看一点就没有过审了..那我就详细讲一下递推而把记搜删掉好了，毕竟已经有记搜题解了，但还没有其它的递推题解。
用 $f_{u,i}$ 表示以 $u$ 为起点，$i$ 的第 $j$ 位为 $1$ 表示还没有收集 $j$ 号光玉（不包括 $u$ 号节点），的最短路径。
转移方程：
$f_{u,i}=\min\{f_{v,i\ xor\ 1<<a_u}+w\}\ \forall(u,v,w)\in E$
初始化：
$f_{u,1<<a_u}=0$
由于可能是稠密图，用邻接矩阵存边即可。
参考代码：
```
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,k,a[110],f[110][1<<13],g[110][110],ans=0x3f3f3f3f;
int main()
{
int i,u,v;
cin>>n>>m>>k;
memset(g,0x3f,sizeof(g));
memset(f,0x3f,sizeof(f));
for (i=1;i<=n;++i)
{
cin>>a[i];
}
for (i=1;i<=m;++i)
{
cin>>u>>v;
cin>>g[u][v];
}
for (i=1;i<=n;++i)
{
f[i][1<<a[i]]=0;
}
for (i=1;i<(1<<k);++i)
{
for (u=1;u<=n;++u)
{
for (v=1;v<=n;++v)
{
if (i&(1<<a[u]))
{
f[u][i]=min(f[u][i],f[v][i^(1<<a[u])]+g[u][v]);
}
}
}
}
for (i=1;i<=n;++i)
{
ans=min(ans,f[i][(1<<k)-1]);
}
if (ans==0x3f3f3f3f)
{
cout<<"Ushio!";
}
else
{
cout<<ans;
}
return 0;
}
```