AcWing 5383. 收集饰品
原题链接
困难
作者:
开始独自升级
,
2024-01-19 22:57:20
,
所有人可见
,
阅读 44
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=110,M=1<<20;
const LL INF=0x3f3f3f3f3f3f3f3fLL;
int n,m,b;
struct Node{
int state,x,k;
bool operator<(const Node&t)const
{
return k<t.k;
}
}r[N];
LL f[M];
int main()
{
cin>>n>>m>>b;
int final = (1<<m) - 1;
for(int i=1;i<=n;i++)
{
int state=0;
int a,b,c;
cin>>a>>b>>c;
while(c--)
{
int e;
cin>>e;
state|=1<<e - 1;
}
r[i]={state,a,b};
}
sort(r+1,r+1+n);
memset(f,0x3f,sizeof f);
f[0]=0;
LL res=INF;
for(int i=1;i<=n;i++)
{
for(int j=0;j<=final;j++)
{
int t=j|r[i].state;
f[t]=min(f[t],f[j]+r[i].x);
}
res=min(res,f[final]+(LL)r[i].k*b);
}
if(res==INF) res=-1;
cout<<res<<endl;
return 0;
}