记录编号	352990	评测结果	AWAAA
题目名称	[HAOI 2005]希望小学	最终得分	80
用户昵称	霓虹灯下的码农	是否通过	未通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-11-17 19:36:27	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<vector>
using namespace std;

int cost[50][50];

struct u
{
     int boy,girl;	
};

u a[50];
int n,b1,b2,b3,g1,g2,g3;

void floyd()
{
	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((!cost[i][j] || cost[i][j]>cost[i][k]+cost[k][j])&& cost[i][k] && cost[k][j])
					{
						cost[i][j]=cost[i][k]+cost[k][j];
					}
				}
			}
		}
	}
}
int main()
{
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	cin>>n>>b1>>b2>>b3>>g1>>g2>>g3;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].boy;
	}
	for(int i=1;i<=n;i++)
	{
		cin>>a[i].girl;
	}
	int k;
	cin>>k;
	
	for(int i=1;i<=k;i++)
	{
		int ai,bi,si1,si2,si3;
		cin>>ai>>bi>>si1>>si2>>si3;
		cost[ai][bi]=a[ai].boy*(si1*b1+si2*b2+si3*b3)+a[ai].girl*(si1*g1+si2*g2+si3*g3);
		cost[bi][ai]=a[bi].boy*(si1*b1+si2*b2+si3*b3)+a[bi].girl*(si1*g1+si2*g2+si3*g3);
		
	}
	floyd();
	int t;
	int minn=1<<30;
	for(int i=1;i<=n;i++)  
	{
		int Sum=0;
		for(int j=1;j<=n;j++) Sum+=cost[j][i];
		if(Sum<minn)
		{
			minn=Sum;
			t=i;
		}
	}
	cout<<t;
	fclose(stdin);
	fclose(stdout);
	return 0;
}