记录编号	15706	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	.Xmz	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2010-03-25 12:15:24	内存使用	0.27 MiB

#include <iostream>
#include <fstream>
#include <cstdio>
#include <cstring>

using namespace std;

const int oo=200000000;
int n,b1,b2,b3,g1,g2,g3;
int x[32],y[32];
int k;
int fx[32][32],fy[32][32];

void init()
{
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	scanf("%d%d%d%d%d%d%d",&n,&b1,&b2,&b3,&g1,&g2,&g3);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=n;j++)
		{
			if (i!=j)
			{
				fx[i][j]=oo;
				fy[i][j]=oo;
			}
		}
	
	for (int i=1;i<=n;i++)  scanf("%d",&x[i]);
	for (int i=1;i<=n;i++)  scanf("%d",&y[i]);
	scanf("%d",&k);
	int a,b,t1,t2,t3;
	for (int i=1;i<=k;i++)
	{
		scanf("%d%d%d%d%d",&a,&b,&t1,&t2,&t3);
		fx[a][b]=b1*t1+b2*t2+b3*t3;
		fx[b][a]=b1*t1+b2*t3+b3*t2;
		fy[a][b]=g1*t1+g2*t2+g3*t3;
		fy[b][a]=g1*t1+g2*t3+g3*t2;
	}
}

void floydx()
{
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (fx[i][j]>fx[i][k]+fx[k][j])
					fx[i][j]=fx[i][k]+fx[k][j];
}

void floydy()
{
	for (int k=1;k<=n;k++)
		for (int i=1;i<=n;i++)
			for (int j=1;j<=n;j++)
				if (fy[i][j]>fy[i][k]+fy[k][j])
					fy[i][j]=fy[i][k]+fy[k][j];
}

int main()
{
	init();
	floydx();
	floydy();
	int ans=oo,np=0;
	for (int i=1;i<=n;i++)
	{
		int s=0;
		for (int j=1;j<=n;j++)
		{	
			s+=fx[j][i]*x[j];
			s+=fy[j][i]*y[j];
		}
		if (s<ans)
		{
			ans=s;
			np=i;
		}
	}
		printf("%d\n",np);
	return 0;
}