记录编号	52721	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2013-02-13 19:36:15	内存使用	0.32 MiB

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
using namespace std;
const int NSIZE=38;
int leng[NSIZE][NSIZE]={0};
int n;
int bp,bu,bd,gp,gu,gd;//男/女生平/上/下的时间
int boy[NSIZE]={0},girl[NSIZE]={0};//人数
void floyd(void){
	int i,j,k;
	for(k=1;k<=n;k++){
		for(i=1;i<=n;i++){
			for(j=1;j<=n;j++){
				if(leng[i][k]+leng[k][j]<leng[i][j]) leng[i][j]=leng[i][k]+leng[k][j];
			}
		}
	}
}
int count(int x){
	int sum=0;
	for(int i=1;i<=n;i++) sum+=leng[i][x];
	return sum;
}
int main(){
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	scanf("%d%d%d%d%d%d%d",&n,&bp,&bu,&bd,&gp,&gu,&gd);
	int i,j;
	for(i=1;i<=n;i++){
		for(j=1;j<=n;j++){
			if(i==j) continue;
			leng[i][j]=0xffffff;
		}
	}
	for(i=1;i<=n;i++) scanf("%d",&boy[i]);
	for(i=1;i<=n;i++) scanf("%d",&girl[i]);
	int m;//道路数
	int a,b,ping,up,down;//对应道路的5个参数
	scanf("%d",&m);
	int temp;
	for(i=1;i<=m;i++){
		scanf("%d%d%d%d%d",&a,&b,&ping,&up,&down);
		temp=boy[a]*(bp*ping+bu*up+bd*down)+girl[a]*(gp*ping+gu*up+gd*down);
		leng[a][b]=temp;
		temp=boy[b]*(bp*ping+bu*down+bd*up)+girl[b]*(gp*ping+gu*down+gd*up);
		leng[b][a]=temp;
	}
	floyd();
	int min=0xffffff,ans=0;
	for(i=1;i<=n;i++){
		temp=count(i);
		if(temp<min){
			min=temp;
			ans=i;
		}
	}
	printf("%d\n",ans);
	return 0;
}