lance.h

lance

0%

cf1487e

发表于 更新于 分类于

Cheap Dinner

需要作四次选择，选4类物品，1与2，2与3，3与4间有冲突。
直接想到的是多层的最短路和网络流，但一建边就是。。

所以贪心暴力即可。
从第一层出发，如1到2，为每个2类物找到最小的1类物，更新其值即可。
先对1类物排序，每次寻找时，从小遍历1类，直到找到一个不冲突的，更新，如果所有都冲突，值为inf。

处理三层即可。答案是第四层值中最小的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<bits/stdc++.h>
#define MP make_pair
#define per() int idkvwo;cin>>idkvwo;while(idkvwo--)
using namespace std;
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3fll;
inline int read(){int ret = 0, sgn = 1;char ch = getchar();while(ch < '0' || ch > '9'){if(ch == '-')sgn = -1;ch = getchar();} while (ch >= '0' && ch <= '9'){ret = ret*10 + ch - '0';ch = getchar();}return ret*sgn;}
struct ui{int val;int pos;bool operator<(const ui b)const{return this->val<b.val;}};
const int maxn=150009;
ui a[maxn];
map<int,int> bp[maxn];
ui b[maxn];
map<int,int> cp[maxn];
ui c[maxn];
map<int,int> dp[maxn];
ui d[maxn];
void handle(ui *A,ui *B,map<int,int> * BP,int lena,int lenb){
  sort(A+1,A+1+lena);
  for(int i=1;i<=lenb;++i){
    int tag=0;
    for(int j=1;j<=lena;j++){
      if(BP[i][A[j].pos]==0){
        B[i].val=min(inf,B[i].val+A[j].val);
        tag=1;
        break;
      }
    }
    if(tag==0){
      B[i].val=inf;
    }
  }
}
int main()
{
  std::ios::sync_with_stdio(false);std::cin.tie(0);
  int n1,n2,n3,n4;
  cin>>n1>>n2>>n3>>n4;
  for(int i=1;i<=n1;++i){
    cin>>a[i].val;
    a[i].pos=i;
  }
  for(int i=1;i<=n2;++i){
    cin>>b[i].val;
    b[i].pos=i;
  }
  for(int i=1;i<=n3;++i){
    cin>>c[i].val;
    c[i].pos=i;
  }
  for(int i=1;i<=n4;++i){
    cin>>d[i].val;
    d[i].pos=i;
  }
  int m1,m2,m3;
  cin>>m1;
  int x,y;
  for(int i=1;i<=m1;++i){
    cin>>x>>y;
    bp[y][x]=1;
  }
  cin>>m2;
  for(int i=1;i<=m2;++i){
    cin>>x>>y;
    cp[y][x]=1;
  }
  cin>>m3;
  for(int i=1;i<=m3;++i){
    cin>>x>>y;
    dp[y][x]=1;
  }
  //handle(int *A,int *B,map<int,int> * BP,int lena,int lenb)
  handle(a,b,bp,n1,n2);
  handle(b,c,cp,n2,n3);
  handle(c,d,dp,n3,n4);
  int mi=inf;
  for(int i=1;i<=n4;++i){
    mi=min(mi,d[i].val);
  }
  if(mi==inf){
    cout<<-1<<endl;
  }else 
      cout<<mi<<endl;
}