记录编号	177912	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	炽烈的爱	是否通过	通过
代码语言	C++	运行时间	0.011 s
提交时间	2015-08-12 21:07:48	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
using namespace std;
int n,k,sum=0x7fffffff;
int b1,b2,b3,g1,g2,g3,ss;
int aa[31],bb[31],dis1[31][31],dis2[31][31];
int main()
{
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	memset(dis1,0x2f,sizeof(dis1));
	memset(dis2,0x2f,sizeof(dis2));
	scanf("%d",&n);
	scanf("%d%d%d",&b1,&b2,&b3);
	scanf("%d%d%d",&g1,&g2,&g3);
	for(int t=1;t<=n;++t)
		scanf("%d",&aa[t]);
	for(int i=1;i<=n;++i)
		scanf("%d",&bb[i]);
	scanf("%d",&k);
	for(int i=1;i<=k;++i)
	{
		int x,y,z,w,h;
		scanf("%d%d%d%d%d",&x,&y,&z,&w,&h);
		dis1[x][y]=aa[x]*(z*b1+w*b2+h*b3);
		dis1[y][x]=aa[y]*(z*b1+h*b2+b3*w);
		dis2[x][y]=bb[x]*(z*g1+w*g2+h*g3);
		dis2[y][x]=bb[y]*(z*g1+h*g2+w*g3);
	}
	for(k=1;k<=n;++k)
		for(int i=1;i<=n;++i)
			for(int j=1;j<=n;++j)
			{
				if(dis1[i][j]>dis1[i][k]+dis1[k][j])
					dis1[i][j]=dis1[i][k]+dis1[k][j];
				if(dis2[i][j]>dis2[i][k]+dis2[k][j])
					dis2[i][j]=dis2[i][k]+dis2[k][j];
			}
	for(k=1;k<=n;++k)
	{
		int ans=0;
		for(int i=1;i<=n;++i)
			if(i!=k)
				ans+=dis1[i][k]+dis2[i][k];
		if(ans<sum)
		{
			sum=ans;
			ss=k;
		}
	}
	printf("%d\n",ss);
}