E. Cheap Dinner

链接戳这
题意：
给定n1,n2,n3,n4种菜肴和m1,m2,m3之间的关系来说明两者不能共存，求最小的花费。
思路：
这题需要数据结构来优化，由于这题符合动态规划的性质，例如abcd数组，a对b数组的影响对c是不具有后效性的，所以我们可以先从a出发递推到d，然后如果暴力咋做呢，也就是对于 ，那复杂度是 ,如何优化呢。我们把每条不符合的边插入到每个b的set中，然后对于a按照val来排序，枚举每个b，然后从小到大枚举a，如果b的set中不存在就可以提前break，这不仔细看复杂度比之前还高啊， 但是由于不符合题目要求的边的个数是 ,也就是第二层循环总共加起来不会超过m，那么复杂度就是
代码：

#include<bits/stdc++.h>
using namespace std;
const int N=200010;
const int INF=0x3f3f3f3f;
int n1,n2,n3,n4;
int m1,m2,m3;
set<int>s1[N],s2[N],s3[N];
struct node{
    int val;
    int id;
    bool operator<(const node&W)const
    {
        return val<W.val;
    }
}a[N],b[N],c[N],d[N];
void solve(node a[],node b[],int n1,int n2,set<int>s[])
{
    sort(a+1,a+1+n1);
    for(int i=1;i<=n2;i++)
    {
        bool flag=0;
        for(int j=1;j<=n1;j++)
        {
            if(s[i].find(a[j].id)==s[i].end())
            {
                flag=1;
                b[i].val=b[i].val+a[j].val;
                break;
            }

        }
            if(!flag)
                b[i].val=INF;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin>>n1>>n2>>n3>>n4;
    for(int i=1;i<=n1;i++)    cin>>a[i].val,a[i].id=i;
    for(int i=1;i<=n2;i++)    cin>>b[i].val,b[i].id=i;
    for(int i=1;i<=n3;i++)    cin>>c[i].val,c[i].id=i;
    for(int i=1;i<=n4;i++)    cin>>d[i].val,d[i].id=i;
    cin>>m1;
    for(int i=0;i<m1;i++)
    {
        int x,y;    cin>>x>>y;
        s1[y].insert(x);
    }
    cin>>m2;
    for(int i=0;i<m2;i++)
    {
        int x,y;     cin>>x>>y;
        s2[y].insert(x);
    }
    cin>>m3;
    for(int i=0;i<m3;i++)
    {
        int x,y; cin>>x>>y;
        s3[y].insert(x);
    }
    solve(a,b,n1,n2,s1);
    solve(b,c,n2,n3,s2);
    solve(c,d,n3,n4,s3);
    int res=INF;
    for(int i=1;i<=n4;i++)
        res=min(res,d[i].val);


    if(res==INF)    res=-1;

    cout<<res<<"\n";

    return 0;
}