题解 P4923 【gcd？人生赢家！】

· · 题解

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

看到范围，很容易想到状压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;
}