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;
}