自动搬运

查看原文

来自洛谷，原作者为

	S_S_H **

搬运于2025-08-24 22:05:43，当前版本为作者最后更新于2019-10-22 20:30:18，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

又一道状压......

推荐做过或没做过的同学们做一下

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;
}

最后祝大家2019CSP NOI XXXOI RP++! ! !