记录编号	124968	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	乌龙猹	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2014-10-07 08:20:27	内存使用	0.30 MiB

#include<cstdio>
using namespace std;

int n,bf,bu,bd,gf,gu,gd;
int k,jl;

int dx[31][31];

struct school
{
	int boy,girl;
};
school a[31];
int main()
{
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	scanf("%d%d%d%d%d%d%d",&n,&bf,&bu,&bd,&gf,&gu,&gd);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].boy);
	for(int i=1;i<=n;i++) scanf("%d",&a[i].girl);
	scanf("%d",&k);
	for(int i=1;i<=k;i++)
	{
		int st,en,l_f,l_u,l_d;
		scanf("%d%d%d%d%d",&st,&en,&l_f,&l_u,&l_d);
		dx[st][en]=a[st].boy*(bf*l_f+bu*l_u+bd*l_d)+a[st].girl*(gf*l_f+gu*l_u+gd*l_d);
		dx[en][st]=a[en].boy*(bf*l_f+bu*l_d+bd*l_u)+a[en].girl*(gf*l_f+gu*l_d+gd*l_u);
	}
	for(int k=1;k<=n;k++)
	{
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				if(i!=j && i!=k && j!=k)
				{
					if((!dx[i][j] || dx[i][j]>dx[i][k]+dx[k][j]) && dx[i][k] && dx[k][j])
						dx[i][j]=dx[i][k]+dx[k][j];
				}
			}
		}
	}
	int minn=0x7f7f7f7f;
	for(int i=1;i<=n;i++)
	{
		int Sum=0;
		for(int j=1;j<=n;j++) Sum+=dx[j][i];
		if(Sum<minn)
		{
			minn=Sum;
			jl=i;
		}
	}
	printf("%d",jl);
}