- it
- 2019 CCPC哈尔滨 A Artful Paintings
#pragma GCC optimize(3)
#include<bits/stdc++.h>
#define N 3010
#define inf 0x3f3f3f3f
#define eps 1e-5
#define pi 3.141592653589793
#define mod 998244353
#define P 1000000007
#define LL long long
#define pb push_back
#define fi first
#define se second
#define cl clear
#define si size
#define lb lower_bound
#define ub upper_bound
#define bug(x) cerr<<#x<<" : "<<x<<endl
#define mem(x,y) memset(x,0,sizeof(int)*(y+3))
#define sc(x) scanf("%d",&x)
#define scc(x,y) scanf("%d%d",&x,&y)
#define sccc(x,y,z) scanf("%d%d%d",&x,&y,&z)
using namespace std
;
const int M
=12050;
struct side
{int to
,d
,nxt
; } e
[M
],_1
[N
],_2
[N
];
int tag
[N
],fa
[N
],dep
[N
],dis
[N
],la
[N
];
vector
<int>son
[N
];
int n
,m1
,m2
,tot
;
inline void Add(int u
,int v
,int d
){
e
[++tot
]={v
,d
,la
[u
]}; la
[u
]=tot
;
}
inline void Change(int u
,int k
){
tag
[u
]=k
; for (auto i
:son
[u
]) Change(i
,k
);
}
inline void Work(int u
){
for(auto i
:son
[u
]){dep
[i
]=dep
[u
]+1; Work(i
); }
}
inline void Cut(int u
){
int v
=fa
[u
];
int l
=son
[v
].size();
for(int i
=0;i
<l
;i
++) if(u
==son
[v
][i
]){
for(int j
=i
;j
<l
-1;j
++) son
[v
][j
]=son
[v
][j
+1];
son
[v
].pop_back();
break;
}
fa
[u
]=0;
}
inline void Link(int v
,int u
){
dep
[v
]=dep
[u
]+1; fa
[v
]=u
;
Work(v
);
son
[u
].push_back(v
);
}
inline bool
Lca(int u
,int goal
){
if(u
==goal
) return 1;
for(auto i
:son
[u
]) if (Lca(i
,goal
)) return 1;
return 0;
}
inline bool
Spfa(){
queue
< int > q
; q
.push(1);
memset(dis
,127/3,sizeof(dis
));
dis
[1]=0;tag
[1]=dep
[1]=1;
while(!q
.empty()){
int u
=q
.front();q
.pop();
if(!tag
[u
]) continue;
for(int j
=la
[u
];j
;j
=e
[j
].nxt
){
int v
=e
[j
].to
,d
=e
[j
].d
;
if(dis
[v
]>dis
[u
]+d
){
if(Lca(v
,u
)) return 1;
dis
[v
]=dis
[u
]+d
;
q
.push(v
);
Change(v
,0);
tag
[v
]=1;
Cut(v
);
Link(v
,u
);
}
}
}
return 0;
}
bool
go(int x
){
tot
=0;
for(int i
=0;i
<=n
;i
++) son
[i
].clear(),fa
[i
]=tag
[i
]=dep
[i
]=la
[i
]=0;
for(int i
=1;i
<=n
;i
++)Add(i
,i
-1,0),Add(i
-1,i
,1);
for(int i
=1;i
<=m1
;i
++) Add(_1
[i
].d
,_1
[i
].to
-1,-_1
[i
].nxt
);
for(int i
=1;i
<=m2
;i
++) Add(_2
[i
].to
-1,_2
[i
].d
,-_2
[i
].nxt
+x
);
Add(0,n
,x
); Add(n
,0,-x
);
return 1-Spfa();
}
int main()
{
int T
;
sc(T
);
while(T
--){
sccc(n
,m1
,m2
);
for(int i
=1;i
<=m1
;i
++) sccc(_1
[i
].to
,_1
[i
].d
,_1
[i
].nxt
);
for(int i
=1;i
<=m2
;i
++) sccc(_2
[i
].to
,_2
[i
].d
,_2
[i
].nxt
);
int l
=0,r
=n
,ans
;
while(l
<=r
){
int t
=l
+r
>>1;
if (go(t
)) ans
=t
,r
=t
-1;
else l
=t
+1;
}
printf("%d\n",ans
);
}
return 0;
}
