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
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156

/*
hdu3311
斯坦纳树+SPFA+状压DP 

二进制枚举子集：

for (int i = s; i; i = (i - 1) &ｓ)

i - 1使得最后一个1变成0，这个1之后的0全部变成1，
&s将原来是0的位变回0，原来是1的位就不断变成0 
 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
using namespace std;
template<typename T>
inline void Minto(T& a,const T& b){if(b<a)a=b;}
template<typename T>
bool read(T& w)
{
	char r;int f=1;
	for(r=getchar();r!=-1&&r!='-'&&(r<48||r>57);r=getchar());
	if(r=='-')r=getchar(),f=-1;
	if(r==-1)return false;
	for(w=0;r>=48&&r<=57;r=getchar())w=w*10+r-48;
	w*=f;
	return true;
}
template<typename T>
void write(T w,char c=0)
{
	if(w<0)w=-w,putchar('-');
	if(w>9)write(w/10);
	putchar(w%10+48);
	if(c)putchar(c);
}
template<typename T,int size>
struct QUE
{
	T ary[size+1];
	int f,t,cnt;
	void clear(){f=t=cnt=0;}
	bool empty(){return cnt==0;}
	void push(const T& w){ary[t++]=w,++cnt;if(t==size)t=0;}
	void pop(){++f,--cnt;if(f==size)f=0;}
	T front(){return ary[f];}
};
const int maxn=13;
const int maxm=1003;
const int maxp=5003;
const int maxs=1<<6;
const int inf=2147483647;
int n,m,p;
struct EDGE
{
	int to,nxt,w;
	void init(int too,int nxtt,int ww)
	{
		to=too,nxt=nxtt,w=ww;
	}
}edge[(maxn+maxm+maxp)<<1];
int ek,head[maxn+maxm];
inline void addEdge(int k,int v,int w)
{
	edge[++ek].init(v,head[k],w);
	head[k]=ek;
}
int full;
void input()
{
	full=(1<<(n+1))-1;
	ek=0;
	memset(head,0,(n+m+1)*sizeof(int));
	for(int i=1,x;i<=n+m;++i)
	{
		read(x);
		addEdge(0,i,x);
		addEdge(i,0,x);
	}
	for(int i=1,a,b,c;i<=p;++i)
	{
		read(a),read(b),read(c);
		addEdge(a,b,c);
		addEdge(b,a,c);
	}
}
int d[maxn+maxm][maxn+maxm];
bool in[maxn+maxm];
QUE<int,maxn+maxm> q;
void SPFA()
{
	for(int k=0;k<=n+m;++k)
	{
		for(int j=0;j<=n+m;++j)
			d[k][j]=inf;
		d[k][k]=0;
		q.clear();
		q.push(k);
		in[k]=true;
		while(!q.empty())
		{
			int ff=q.front();q.pop();in[ff]=false;
			for(int i=head[ff];i;i=edge[i].nxt)
			{
				int v=edge[i].to;
				if(d[k][ff]!=inf&&d[k][ff]+edge[i].w<d[k][v])
				{
					d[k][v]=d[k][ff]+edge[i].w;
					if(!in[v])
						in[v]=true,q.push(v);
				}
			}
		}
	}
}
int f[maxn+maxm][maxs],bit[maxn];
void SteinerTree()
{
	for(int i=0;i<=n+m;++i)
		for(int j=0;j<=full;++j)
			f[i][j]=inf;
	for(int i=0;i<=n;++i)
		bit[i]=1<<i,f[i][bit[i]]=0;
	for(int i=0;i<=n;++i)
		for(int j=0;j<=n+m;++j)
			f[j][bit[i]]=d[i][j];
	for(int i=0;i<=full;++i)//枚举状态 
	if(i&(i-1))
	{
		for(int j=0;j<=n+m;++j)//枚举根 
		{
			for(int k=i;k;k=(k-1)&i)//枚举子集 
				if(f[j][k]!=inf&&f[j][i-k]!=inf)
					Minto(f[j][i],f[j][k]+f[j][i-k]);
		}
		for(int j=0;j<=n+m;++j)//枚举另一个点 
			for(int k=0;k<=n+m;++k)//枚举另一个点 
				if(f[k][i]!=inf&&d[j][k]!=inf)
					Minto(f[j][i],f[k][i]+d[j][k]);
	}
}
int main()
{
	freopen("hdu3311_1.in","r",stdin);
	//freopen("hdu3311.out","w",stdout);
	while(read(n),read(m),read(p))
	{
		input();
		SPFA();
		SteinerTree();
		write(f[0][full],'\n');
	}
	return 0;
}