Kefa and Dishes(CodeForces580D)【状态压缩DP】

状态压缩DP裸题，比赛的时候没反应过来，进行了n次枚举起点的solve,导致超时。

#include<cstdio>

#include<iostream>

#include<vector>

#include<cstring>

using namespace std;

int n,m,k;

int cost[][],val[];

int a,b,c;

long long dp[<<][];

vector<int> hhh[];

int judge(int x){

    int res=;

    while(x!=){

        if(x&)

            res++;

        x>>=;

    }

    return res;

}

void init(){

    for(int i=;i<(<<);i++)

        hhh[judge(i)].push_back(i);

}

long long solve(){

    for(int s=;s<(<<n);s++)

        fill(dp[s],dp[s]+n,);

    for(int i=;i<n;i++)

        dp[<<i][i]=-val[i];

    for(int jj=;jj<=n;jj++){

        for(int jjj=;jjj<hhh[jj].size();jjj++){

            int j=hhh[jj][jjj];

            for(int i=;i<n;i++){

                   if(dp[j][i]==||(j&(<<i))==)

                    continue;

                int tt=((<<n)-)^(j);

                for(int k=;k<n;k++)

                    if((j&(<<k))==)

                        dp[j|(<<k)][k]=min(dp[j|(<<k)][k],dp[j][i]+cost[i][k]-val[k]);

            }

        }

    }

    long long res=;

    for(int j=;j<=(<<n)-;j++){

        if(judge(j)==m)

            for(int i=;i<n;i++)

                res=min(res,dp[j][i]);

    }

    return res;

}

int main(){

    scanf("%d%d%d",&n,&m,&k);

    init();

    for(int i=;i<=n;i++)

        scanf("%d",&val[i-]);

    while(k--){

        scanf("%d%d%d",&a,&b,&c);

        cost[a-][b-]=-c;

    }

    long long ans=;

    printf("%lld",-solve());

    return ;

}