题目链接： http://acm.hdu.edu.cn/showproblem.php?pid=5545
题意：有N个村庄， M 个战场； $ 1 <=N,M <= 10^5 $;
其中曹操会从第i个村庄中选出若个人 在x[i]战场为其作战， 同时第i个村庄也会有相同的人数在y[i]战场为袁绍作战；
每个战场i 有对应的重要度w[i]，w[i]的值为 0,1,2；
w[i]为2的战场，要求曹操的兵数（从村庄得到的） 严格大于 袁绍的兵的数量；
w[i]为1的战场，曹操的兵数不少于袁绍的兵即可；
w[i]为0的兵，没限制要求；
并且每个村庄派出一个兵有对应的花费c[i], 问要使得曹操在所有的战场士兵人数满足上面的要求，曹操至少花费为多少/
思路：
以贪心的思想很容易想到应该从重要程度为2的村庄开始考虑，如果村庄 i满足w[i]等于2，那么曹操先往该村庄派遣一个士兵；那么由题意知，在y[i]战场 袁绍的并多了1个；怎么办？
是不是曹操就需要往y[i]战场添加士兵呢？
不一定，需要看y[i]战场的重要程度，如果重要程度为0呢~~
所以只需要**递推**到重要程度为0的战场即可；
那怎么考虑花费最少呢？
以每个村庄的**价格**作为边的权值，求出所有w[i]为2的点到最近的w[j] = 0的最短路即可；
但如果直接建边，以重要度为2的战场作为源点spfa到重要度为0的重点，得到的将是曹操为重要度为0的战场的花费；所以反向建边，开始将W[i] = 0的放入队列即可；
spfa解法：
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<bits/stdc++.h>
using namespace std;
#define rep0(i,l,r) for(int i = (l);i < (r);i++)
#define rep1(i,l,r) for(int i = (l);i <= (r);i++)
#define rep_0(i,r,l) for(int i = (r);i > (l);i--)
#define rep_1(i,r,l) for(int i = (r);i >= (l);i--)
#define MS0(a) memset(a,0,sizeof(a))
#define MS1(a) memset(a,-1,sizeof(a))
#define MSi(a) memset(a,0x3f,sizeof(a))
#define pb push_back
#define MK make_pair
#define A first
#define B second
#define clear0 (0xFFFFFFFE)
#define inf 0x3f3f3f3f
#define INF 0x3f3f3f3f3f3f3f3f
#define eps 1e-8
#define mod 1000000007
#define zero(x) (((x)>0?(x):-(x))<eps)
#define bitnum(a) __builtin_popcount(a)
#define lowbit(x) (x&(-x))
#define K(x) ((x)*(x))
#define debug(x) printf(" ---- %d\n",x)
typedef pair<int,int> PII;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
template<typename T>
void read1(T &m)
{
T x = ,f = ;char ch = getchar();
while(ch <'' || ch >''){ if(ch == '-') f = -;ch=getchar(); }
while(ch >= '' && ch <= ''){ x = x* + ch - '';ch = getchar(); }
m = x*f;
}
template<typename T>
void read2(T &a,T &b){read1(a);read1(b);}
template<typename T>
void read3(T &a,T &b,T &c){read1(a);read1(b);read1(c);}
template<typename T>
void out(T a)
{
if(a>) out(a/);
putchar(a%+'');
}
inline ll gcd(ll a,ll b){ return b == ? a: gcd(b,a%b); }
inline ll lcm(ll a,ll b){ return a/gcd(a,b)*b; }
template<class T1, class T2> inline void gmax(T1& a, T2 b){ if(a < b) a = b;}
template<class T1, class T2> inline void gmin(T1& a, T2 b){ if(a > b) a = b;}
const int dx[] = {-,,,}, dy[] = {,,,-};
const int maxn = ;
int head[maxn], tot;
ll dist[maxn], vs[maxn];
void init(){
MS0(head);
MSi(dist);
tot = ;
}
struct edge{
int to, w, nxt;
} e[maxn << ]; void ins(int u,int v,int w)
{
e[++tot].nxt = head[u];
e[tot].to = v;
e[tot].w = w;
head[u] = tot;
}
int x[maxn], y[maxn], c[maxn], w[maxn];
int que[maxn];
ll build(int n, int m)
{
int h = , t = ;
rep1(i,,n){
ins(y[i], x[i], c[i]);
if(w[y[i]] == && dist[y[i]] == INF)
que[t++] = y[i], dist[y[i]] = ;
}
while(h < t){
int u = que[h++]; vs[u] = ;
for(int id = head[u]; id; id = e[id].nxt){
int v = e[id].to, w = e[id].w;
if(dist[v] > dist[u] + w){
dist[v] = dist[u] + w;
if(vs[v] == ){
que[t++] = v;
vs[v] = ;
}
}
}
}
ll ans = ;
for(int i = ; i <= m; i++) if(w[i] == ){
if(dist[i] == INF) return -;
ans += dist[i];
}
return ans;
}
int main()
{
//freopen("data.txt","r",stdin);
//freopen("out.txt","w",stdout);
int T, kase = ;
scanf("%d",&T);
while(T--){
init();
int n, m;
read2(n, m);
rep1(i,,n) read1(x[i]);
rep1(i,,n) read1(y[i]);
rep1(i,,n) read1(c[i]);
rep1(i,,m) read1(w[i]);
printf("Case #%d: %I64d\n",kase++, build(n, m));
}
return ;
}