题解 P4962 【朋也与光玉】
又一道状压......
推荐做过或没做过的同学们做一下
P4802 [CCO 2015]路短最
P4772 灰化肥，会挥发
这两道状压题，和这个题很像，推荐食用我的题解......
题目简化：说的很清楚了，每个点一个颜色，找到一条最短的点数为 k 、恰好经过
全部 k 种颜色的路径，求出这条路径的长度。
数据范围2 ≤ k ≤ 13可以状压
那我们是用递推还是搜索？貌似很麻烦......其实就是不会
因为和P4802和P4772相比，此题唯一的不同就是节点不再具有唯一性
（很简单）
就是我这个颜色可以由很多节点转移而来，转移时枚举转移点无法考虑边的长度
本蒟蒻只能考虑记忆化搜索
定义状态check[ S ][ t ]表示已取节点状态为S以t为节点的情况下的最长路
因为走过的不可以再走，就相当于这个图中所有已有状态的节点都已经不可走
所以该状态与从那条路径来没有关系，满足无后效性。我们这里的check数组可以
作为记忆化数组来用，如果现状态的值比它大，就可以舍弃掉。
分析到这里，我们O( n ! / 玄学 )代码已经构思完了
很简洁的代码：
#include<iostream>
#include<cstdio>
const int inf=2147483647;
const int maxm=(1<<14)-1;
using namespace std;
int n,m,k,ans=inf,color[110],map[110][110],check[110][(1<<14)];
void dfs(int now,int len,int s,int num){//表示：当前节点，已有光玉个数，现状态，路径和
if((s&(1<<color[now]))||ans<=num||check[now][s]<=num) return;//记忆化
if(len==k){
ans=num;
return;
}
check[now][s]=num;
for(int i=1;i<=n;i++)
if(map[now][i]!=inf)
dfs(i,len+1,s|(1<<color[now]),num+map[now][i]);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for(int i=1;i<=n;i++)
scanf("%d",&color[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
map[i][j]=inf;
for(int i=1;i<=m;i++){
int u,v,c;
scanf("%d%d%d",&u,&v,&c);
map[u][v]=c;
}
for(int i=1;i<=n;i++)
for(int j=0;j<=(1<<k)-1;j++)
check[i][j]=inf;
for(int i=1;i<=n;i++)
check[i][1<<color[i]]=0;
for(int i=1;i<=n;i++)
dfs(i,1,0,0);
ans==inf?printf("Ushio!"):printf("%d",ans);//异端的三目运算
return 0;
}