记录编号	430993	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	Fisher.	是否通过	通过
代码语言	C++	运行时间	0.003 s
提交时间	2017-07-30 22:05:45	内存使用	0.32 MiB

#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
inline int read(){
	int x=0,f=1;char c=getchar();
	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
	while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}
	return x*f;
}
const int maxn=40;
const int maxm=110;
int nan[maxn],nv[maxn];
int bs,bx,bp,gs,gx,gp;
int n,m;
queue<int>duilie;
vector<int>g[maxn];
vector<int>w[maxn];
int minn=0x7fffffff,pos;
int d[maxn];
int ok[maxn];
int tot[maxn]; 
inline void spfa(int st){
	memset(d,0x3f3f3f3f,sizeof(d));
	ok[st]=1;
	duilie.push(st);
	d[st]=0;
	while(!duilie.empty()){
		int u=duilie.front();duilie.pop();
		for(int i=0;i<g[u].size();i++){
			int v=g[u][i];
			if(d[v]>d[u]+w[u][i]){
				d[v]=d[u]+w[u][i];
				if(!ok[v]){
					ok[v]=1;
					duilie.push(v); 
				}
			}
		}
		ok[u]=0;
	}
}
//int f[maxn][maxn];
int main(){
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	n=read();bp=read();bs=read();bx=read();gp=read();gs=read();gx=read();
	for(int i=1;i<=n;i++){nan[i]=read();}
	for(int i=1;i<=n;i++){nv[i]=read();}
	m=read();
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),p=read(),s=read(),x=read();
		g[u].push_back(v);
		g[v].push_back(u);
		int w1=nan[u]*(p*bp+s*bs+x*bx)+nv[u]*(p*gp+s*gs+x*gx);
		w[u].push_back(w1);   
		int w2=nan[v]*(p*bp+s*bx+x*bs)+nv[v]*(p*gp+s*gx+x*gs);
		w[v].push_back(w2); 
	}
	/*for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			f[i][j]=0x3f3f3f3f;
		}
	}
	for(int i=1;i<=m;i++){
		int u=read(),v=read(),p=read(),s=read(),x=read();
		f[u][v]=nan[u]*(p*bp+s*bs+x*bx)+nv[u]*(p*gp+s*gs+x*gx);
		f[v][u]=nan[v]*(p*bp+s*bx+x*bs)+nv[v]*(p*gp+s*gx+x*gs);
	}
	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&&f[i][j]>f[i][k]+f[k][j]){
					f[i][j]=f[i][k]+f[k][j];
				}
			}
		}
	}
	for(int i=1;i<=n;i++){
		int sum=0;
		for(int j=1;j<=n;j++){
			if(i!=j&&f[j][i]!=0x3f3f3f3f){
				sum+=f[j][i];
			}
		}
		if(sum<minn){
			minn=sum;
			pos=i;
		}
	}*/
	for(int i=1;i<=n;i++){
		spfa(i);
		for(int j=1;j<=n;j++){
			if(d[j]!=0x3f3f3f3f)tot[j]+=d[j];
		}
	}
	for(int i=1;i<=n;i++){
		if(minn>tot[i]){minn=tot[i];pos=i;}
	}
	printf("%d\n",pos);
	return 0;
}