P4923

题目传送门

思路

由于 $n \le 200$，我们可以用 Floyd 预处理出任意两点间的最短路。

注意到 $m \le 12$，所以考虑状压 DP。

可以类比分层图最短路的思想，将剩余传送次数作为状态的一维。设 $dp[s][i][j]$ 表示获得宝物集合为 $s$，当前位于第 $i$ 个宝物位置，剩余 $j$ 次传送次数时的最小时间。

设 $u$ 为当前宝物，$v$ 为下一个满足前置条件的宝物，$gain$ 为获得 $v$ 后达成成就奖励的传送次数，那么转移方程为：

$$
dp[s’][v][j_{next}]=\min \begin{cases}
dp[s][u][j]+dis[p_u][p_v] & \text{非传送，} j_{next}=j+gain \\
dp[s][u][j] & \text{传送，} j_{next}=j-1+gain，j \ge 1
\end{cases}
$$

其中 $s’=s \cup {v}$，$p_u$ 指的是第 $u$ 个宝物在地图上的实际节点编号，$p_v$ 类似，$dis$ 数组表示地图节点间的距离。

宝物的前置要求和成就奖励可以在输入的时候预处理，转移的时候就能 $O(1)$ 判断了。

时间复杂度为 $O(n^3 + 2^m \cdot m^2 \cdot k)$。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int inf=0x3f3f3f3f3f3f3f3f;
int n,m,k,s,e,st,ans=inf;
int need[15],a[15],p[15],dis[205][205],pre[15],dp[1<<12][12][20],sum[1<<12];
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>n>>m>>k>>s;
	for (int i=1;i<=s;i++) {
		int num,x,msk=0;
		cin>>num;
		while (num--)
			cin>>x,x--,msk|=(1<<x);
		need[i]=msk;
	}
	for (int i=1;i<=s;i++)
		cin>>a[i];
	for (int i=0;i<m;i++)
		cin>>p[i];
	cin>>e;
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
			if (i!=j) dis[i][j]=inf;
	for (int i=1,u,v,w;i<=e;i++)
		cin>>u>>v>>w,dis[u][v]=min(dis[u][v],w),dis[v][u]=min(dis[v][u],w);
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
	for (int i=0;i<m;i++) {
		int num,x,msk=0;
		cin>>num;
		while (num--)
			cin>>x,x--,msk|=(1<<x);
		pre[i]=msk;
	}
	cin>>st;
	for (int msk=0;msk<(1<<m);msk++) {
		int tot=0;
		for (int i=1;i<=s;i++)
			if ((msk&need[i])==need[i]) tot+=a[i];
		sum[msk]=tot;
	}
	memset(dp,0x3f,sizeof(dp));
	for (int i=0;i<m;i++)
		if (pre[i]==0) {
			if (dis[st][p[i]]!=inf) {
				int nt=min(15ll,k+sum[1<<i]);
				dp[1<<i][i][nt]=min(dp[1<<i][i][nt],dis[st][p[i]]);
			}
			if (k>0) {
				int nt=min(15ll,k-1+sum[1<<i]);
				dp[1<<i][i][nt]=min(0ll,dp[1<<i][i][nt]);
			}
		}
	for (int msk=1;msk<(1<<m);msk++)
		for (int u=0;u<m;u++) {
			if (!((msk>>u)&1)) continue;
			for (int t=0;t<=15;t++) {
				if (dp[msk][u][t]==inf) continue;
				for (int v=0;v<m;v++) {
					if ((msk>>v)&1) continue;
					if ((msk&pre[v])!=pre[v]) continue;
					int nmsk=msk|(1<<v);
					if (dis[p[u]][p[v]]!=inf) {
						int nt=min(15ll,t+(sum[nmsk]-sum[msk]));
						dp[nmsk][v][nt]=min(dp[nmsk][v][nt],dp[msk][u][t]+dis[p[u]][p[v]]);
					}
					if (t>0) {
						int nt=min(15ll,t-1+(sum[nmsk]-sum[msk]));
						dp[nmsk][v][nt]=min(dp[nmsk][v][nt],dp[msk][u][t]);
					}
				}
			}
		}
	for (int u=0;u<m;u++)
		for (int t=0;t<=15;t++)
			ans=min(ans,dp[(1<<m)-1][u][t]);
	cout<<ans;
	return 0;
}