记录编号	220705	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2016-01-20 10:22:59	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#define max(a,b) a>b?a:b
int x[33],y[33];
int disb[33][33],disg[33][33];
bool inq[33];
int q[30];
int head,tail;
void add(int a){
	if(!inq[a]){
		q[tail++]=a;
		inq[a]=true;
		if(tail==30)tail=0;
	}
}
void _add(int a){
	if(!inq[a]){
		if(head!=0)q[--head]=a;
		else {
			head = 29;
			q[29] = a;
		}
		inq[a] = true;
	}
}
void del(){
	inq[q[head]]=false;
	head=(head+1)%30;
}
int n;
void spfa(int d[][33],int s){
	memset(inq,0,sizeof(inq));
	memset(q,0,sizeof(q));
	for(int i = 1;i<=n;++i)if(s!=i&&d[s][i]!=1<<20)add(i);
	while(head!=tail){
		int v = q[head];
		for(int i = 1;i<=n;++i){
			if(d[s][v]+d[v][i]<d[s][i]){
				d[s][i]=d[s][v]+d[v][i];
				if(d[s][i]>d[s][q[head]])add(i);
				else _add(i);
			}
		}
		del();
	}
}
int main(){
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	int b1,b2,b3,g1,g2,g3;
	scanf("%d %d %d %d %d %d %d",&n,&b1,&b2,&b3,&g1,&g2,&g3);
	for(int i = 1;i<=n;++i)scanf("%d",x+i);
	for(int i = 1;i<=n;++i)scanf("%d",y+i);
	int k;
	scanf("%d",&k);
	int a,b,s1,s2,s3;
	for(int i = 1;i<=n;++i){
		for(int j = 1;j<=n;++j)
			disb[i][j] = disg[i][j] = 1<<20;
	}
	for(int i = 0;i<k;++i){
		scanf("%d %d %d %d %d",&a,&b,&s1,&s2,&s3);
		disb[a][b]=s1*b1+s2*b2+s3*b3;
		disb[b][a]=s1*b1+s2*b3+s3*b2;
		disg[a][b]=s1*g1+s2*g2+s3*g3;
		disg[b][a]=s1*g1+g2*s3+g3*s2;
	}
	for(int i = 1;i<=n;++i){
		spfa(disb,i);
		spfa(disg,i);
	}
	int mintot = 1<<25,ans = -1;
	for(int i = 1;i<=n;++i){
		int nowtot = 0;
		for(int j = 1;j<=n;++j){
			if(i!=j){
			nowtot+=x[j]*disb[j][i];
			nowtot+=y[j]*disg[j][i];
			}
		}
		if(nowtot<mintot){
			mintot=nowtot;
			ans = i;
		}
	}
	printf("%d\n",ans);
	fclose(stdin);fclose(stdout);
	return 0;
}