记录编号	149312	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2015-02-22 22:49:27	内存使用	0.33 MiB

#include <fstream>
using namespace std;
int n,m,ans;
bool have[31][31]={0};
int x[3],y[3],boy[31],girl[31],f[31][31]={0},g[31][31]={0},way[31][31][3],best=9999999;
int main()
{
	int i,j,k,x1,x2;int time,x3,x4,x5,t;
	ifstream in("hopeschool.in");
	ofstream out("hopeschool.out");
	in>>n;
	for(i=1;i<=3;i++)in>>x[i];
	for(i=1;i<=3;i++)in>>y[i];
	for(i=1;i<=n;i++)in>>boy[i];
	for(i=1;i<=n;i++)in>>girl[i];
	in>>m;
	for(i=1;i<=n;i++)for(j=1;j<=n;j++)f[i][j]=g[i][j]=9999999;
	for(i=1;i<=m;i++)
	{
		in>>x1>>x2>>x3>>x4>>x5;
		//way[x1][x2][1]=x3;
		//way[x1][x2][2]=x4;
		//way[x1][x2][3]=x5;
		//have[x1][x2]=1;
		t=boy[x1]*(x[1]*x3+x[2]*x4+x[3]*x5)+girl[x1]*(y[1]*x3+y[2]*x4+y[3]*x5);
		f[x1][x2]=t;
		t=boy[x2]*(x[1]*x3+x[2]*x5+x[3]*x4)+girl[x2]*(y[1]*x3+y[2]*x5+y[3]*x4);
		f[x2][x1]=t;
		//way[x2][x1][3]=x5;
		//way[x2][x1][2]=x4;
		//way[x2][x1][1]=x3;
		//have[x2][x1]=1;
	}
	/*for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			out<<f[i][j]<<' ';
		}
		out<<endl;
	}*/
	for(i=1;i<=n;i++)
	{
		f[i][i]=0;
		g[i][i]=0;
	}
	for(k=1;k<=n;k++)for(i=1;i<=n;i++)for(j=1;j<=n;j++)
	{
		if(f[i][k]+f[k][j]<f[i][j])f[i][j]=f[i][k]+f[k][j];
	}
	best=9999999;
	for(i=1;i<=n;i++)
	{
		time=0;
		for(j=1;j<=n;j++)
		{
			if(i!=j)
			{
				if(f[i][j]!=9999999)time+=f[j][i];
			}
		}
		//out<<i<<' '<<time<<endl;
		if(time<best)
		{
			best=time;
			ans=i;
		}
	}
	out<<ans<<endl;
	in.close();
	out.close();
	return 0;
}