记录编号	15856	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	Oo湼鞶oO	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2010-04-06 19:54:49	内存使用	0.26 MiB

#include <fstream>

using namespace std;

short n,m,b[3],g[3],ans;
short sb[30][30],sg[30][30];
short x[30],y[30];

void input();
void freud();
void lookfor();
void output();

int main()
{
	input();
	freud();
	lookfor();
	output();
}

void input()
{
	short i,j,k,p,q;
	ifstream fin("hopeschool.in");
	fin>>n;
	for (i=0; i<3; fin>>b[i++]);
	for (i=0; i<3; fin>>g[i++]);
	for (i=0; i<n; fin>>x[i++]);
	for (i=0; i<n; fin>>y[i++]);
	short t[30][30][3]={{{0}}};
	fin>>m;
	for (i=0; i<m; i++)
	{
		fin>>p>>q;
		p--; q--;
		for (j=0; j<3; j++)
			fin>>t[p][q][j];
		t[q][p][0]=t[p][q][0];
		t[q][p][1]=t[p][q][2];
		t[q][p][2]=t[p][q][1];
	}
	fin.close();
	
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
		if (t[i][j][0]+t[i][j][1]+t[i][j][2]>0)	
			for (k=0; k<3; k++)
			{
				sb[i][j]+=t[i][j][k]*b[k]*x[i];
				sg[i][j]+=t[i][j][k]*g[k]*y[i];
			}
		else
		{
			sb[i][j]=32767;
			sg[i][j]=32767;
		}
}

void freud()
{
	short i,j,k;
	for (i=0; i<n; i++)
		for (j=0; j<n; j++)
			for (k=0; k<n; k++)
			{
				if ((sb[j][i]+sb[i][k])<sb[j][k])
					sb[j][k]=sb[j][i]+sb[i][k];
				if ((sg[j][i]+sg[i][k])<sg[j][k])
					sg[j][k]=sg[j][i]+sg[i][k];
			}
}

void lookfor()
{
	short i,j;
	int t,ts=32767;
	for (i=0; i<n; i++)
	{
		t=0;
		for (j=0; j<n; j++)
			t=t+sb[j][i]+sg[j][i];
		if (t<ts)
		{
			ans=i;
			ts=t;
		}
	}
}

void output()
{
	ofstream fout("hopeschool.out");
	fout<<ans+1<<endl;
	fout.close();
}