题解 CF1487E 【Cheap Dinner】

绝顶我为峰 · 2021-02-17 14:19:21 · 题解

无脑暴力题。

考虑合并两组菜品 a,b，一个显然的做法是对于每一个 b_i，找到能和它搭配的 a 中权值最小的（记为 a_j） 来合并，并将 b_i 权值更新为 a_j+b_i。

正确性显然。

然后这个东西可以用 vector+map 搞了，具体来说每一次合并之前 vector 先排序，然后每一个菜品挨个从前往后查找第一个可以匹配的即可。map 用来存限制。

时限 4s，显然可以过。

#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
vector<pair<int,int> > v[5];
int n[5];
map<pair<int,int>,int> mp[5];
int main()
{
    scanf("%d%d%d%d",&n[1],&n[2],&n[3],&n[4]);
    for(register int i=1;i<=4;++i)
        for(register int j=1;j<=n[i];++j)
        {
            int x;
            scanf("%d",&x);
            v[i].push_back(make_pair(x,j));
        }
    for(register int i=2;i<=4;++i)
    {
        int m;
        scanf("%d",&m);
        for(register int j=1;j<=m;++j)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            mp[i][make_pair(x,y)]=1;
        }
    }
    for(register int i=2;i<=4;++i)
    {
        sort(v[i-1].begin(),v[i-1].end());
        for(register int j=0;j<n[i];++j)
        {
            int k=0;
            while(k<n[i-1]&&mp[i][make_pair(v[i-1][k].second,v[i][j].second)])
                ++k;
            if(k==n[i-1])
                v[i][j].first=1<<30;
            else
                v[i][j].first+=v[i-1][k].first;
        }
    }
    sort(v[4].begin(),v[4].end());
    printf("%d\n",v[4][0].first>1e9? -1:v[4][0].first);
    return 0;
}