状压DP
学到一手，位操作时注意超出int用1LL进行位操作。
还有一个就是可以用排序从小到大进行降维。
代码语言：javascript复制#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<math.h>
#include<queue>
using namespace std;
struct node
{
long long m,num,can;//开始WA了后来丧心病狂全部改longlong
}node[105];
long long n,m,b;
bool vis[25];
long long dp[1LL<<20|1];
bool cmp(const struct node &a,const struct node &b)
{
return a.num<b.num;
}
int main()
{
cin>>n>>m>>b;
memset(vis,false,sizeof(vis));
for(int i=0;i<n;i )
{
int t,a;
cin>>node[i].m>>node[i].num>>t;
for(int j=0;j<t;j )
{
cin>>a;
vis[a]=true;
node[i].can|=(1LL<<(a-1));
}
}
int i;
for(i=1;i<=m;i )
if(!vis[i])
break;
if(i!=m 1)
{
cout<<"-1"<<endl;//判-1的情况要注意
}
else
{
long long ans=(1LL<<60);
for(int i=0;i<(1LL<<m);i )
dp[i]=(1LL<<60);
sort(node,node n,cmp);
dp[0]=0;
for(int i=0;i<n;i )
{
for(int j=0;j<(1LL<<m);j )
{
dp[j|node[i].can]=min(dp[j|node[i].can],dp[j] node[i].m);
}
if(dp[(1LL<<m)-1]!=(1LL<<60))
ans=min(ans,dp[(1LL<<m)-1] node[i].num*b);//如果最大没更新说明没有优化，不用算上这个人，否则需要加上b*num
}
cout<<ans<<endl;
}
return 0;
}
