自动搬运

查看原文

来自洛谷，原作者为

	Drawing_Yang **

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

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

以下是正文

首先吐槽一句，这输入有点恶心。

看到范围，很容易想到状压Dp，但又有不同之处，可以直接传送，这样是不是像分层图？

于是考虑Dp+分层图。设$f[s][i][j]$为状态为$s$，最后一个点是第$i$个点，用了$j$次神器或奖励的传送次数。则可以很容易得到

$f[s][i][j]=\min\{f[s'][t][j-1],f[s'][t][j]+g[p[i]][p[j]]\}$

其中$p[i]$表示第$i$个需要到达的节点，$g[i][j]$表示$i,j$的最短路，$s'$是能转移到$s$的状态。

至于成就，读入时先存为一个状态，再在转移前枚举这个状态是否满足成就，当然，更好的方法是预处理出每个状态可以获得的传送次数。

至于宝物的前置要求，同样读入时存为一个状态，在转移前判断这个状态是否满足对应的前置要求，即$t\&(bf[i])$是否等于$bf[i]$，等于则合法。

出题人还是比较良心，没有卡Floyd。

根据这个方程，容易得到代码。

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define lowbit(x) ((x)&-(x))
using namespace std;
struct achievement {
	int s;
	int tis;
} ach[10];
int bf[20];
int a[(1<<12)];
int n,m,K,S,e,st;
int g[205][205];
int p[20],mx;
int f[1<<12][13][13];
void Read() {
	scanf("%d%d%d%d",&n,&m,&K,&S);
	for (int i=1; i<=S; i++) {//成就 
		int t;
		scanf("%d",&t);
		for (int j=1; j<=t; j++) {
			int a;
			scanf("%d",&a);
			ach[i].s|=(1<<(a-1));
		}
	}
	for (int i=1; i<=S; i++) {
		scanf("%d",&ach[i].tis);
		mx+=ach[i].tis;
	}
	for (int i=1; i<=m; i++) {
		scanf("%d",&p[i]);
	}
	scanf("%d",&e);
	for (int i=1; i<=e; i++) {
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		g[x][y]=g[y][x]=min(g[x][y],z);//注意重边 
	}
	for (int i=1; i<=m; i++) {
		int t;
		scanf("%d",&t);
		for (int j=1; j<=t; j++) {
			int a;
			scanf("%d",&a);
			bf[i]|=(1<<(a-1));//前置 
		}
	}
	scanf("%d",&st);
}
void Floyd() {//Floyd 
	for (int i=1; i<=n; i++) g[i][i]=0;
	for (int kk=1; kk<=n; kk++)
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
				g[i][j]=min(g[i][j],g[i][kk]+g[kk][j]);

}
void Dp() {
	memset(f,0x3f,sizeof(f));
	for (int i=1; i<=m; i++) {//初始化 
		if (!bf[i]) {
			f[1<<(i-1)][i][0]=g[st][p[i]]; 
			if (K>1) f[1<<(i-1)][i][1]=0;
		}
	}
	for (int s=0; s<(1<<m); s++) {
		for (int i=s; i; i-=lowbit(i)) {//用lowbit()来枚举，比直接枚举要快 
			for (int j=s-lowbit(i); j; j-=lowbit(j)) {//同理 
				int t1=log2(lowbit(i))+1,t2=log2(lowbit(j))+1;//获取节点 
				if (t1==t2) continue;
				if (((s-lowbit(i))&bf[t1])!=bf[t1]) continue;//判断是否满足前置要求 
				int os=0;
				for (int r=1; r<=S; r++) {//枚举改状态可以获得的传送次数 
					if (((s-lowbit(i))&ach[r].s)==ach[r].s)
						os+=ach[r].tis;
				}
				for (int k=0; k<=K+os; k++) {//更新 
					f[s][t1][k]=min(f[s][t1][k],f[s-lowbit(i)][t2][k]+g[p[t2]][p[t1]]);
					if (k!=0) f[s][t1][k]=min(f[s][t1][k],f[s-lowbit(i)][t2][k-1]);
				}
			}
		}
	}
}
void Print() {
	int ans=0x3f3f3f3f;
	for (int i=1; i<=m; i++) {
		for (int k=0; k<=K+mx; k++)
			ans=min(ans,f[(1<<m)-1][i][k]);
	}
	printf("%d",ans);
}
int main() {
	memset(g,0x3f,sizeof(g));
	Read();
	Floyd();
	Dp();
	Print();
	return 0;
}