记录编号	552289	评测结果	AWWWW
题目名称	[HAOI 2005]希望小学	最终得分	20
用户昵称	Evolt	是否通过	未通过
代码语言	C++	运行时间	0.004 s
提交时间	2020-07-25 12:02:14	内存使用	21.32 MiB

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
typedef unsigned long long ULL;
const int INF = 0x7f;
const int MAXN = 1001;
ULL n,b1,b2,b3,g1,g2,g3,m;
ULL xn[MAXN],yn[MAXN];
ULL g[MAXN][MAXN];
int main () {
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	cin >> n >> b1 >> b2 >> b3 >> g1>>g2 >> g3;
//	scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&b1,&b2,&b3,&g1,&g2,&g3);
	for (int q=1;q<=n;q++) {
		for (int w=1;w<=n;w++) {
			g[q][w]=INF;
		}
		g[q][q]=0;
	}
	for (int q=1;q<=n;q++) {
		cin >> xn[q];
	//	scanf("%lld",&xn[q]);
	}
	for (int q=1;q<=n;q++) {
		cin >> yn[q];
	//	scanf("%lld",&yn[q]);
	}
	cin >> m;
//	scanf("%lld",&m);
	ULL a,b,s1,s2,s3;
	ULL c;
	for (int q=1;q<=m;q++) {
		cin >> a >> b >> s1 >> s2 >> s3;
	//	scanf("%lld%lld%lld%lld%lld",&a,&b,&s1,&s2,&s3);
		g[a][b]=xn[a]*(s1*b1+s2*b2+s3*b3)+yn[a]*(s1*g1+s2*g2+s3*g3);
		g[b][a]=xn[b]*(s1*b1+s2*b2+s3*b3)+yn[b]*(s1*g1+s2*g2+s3*g3);
	}
	for (int k=1;k<=n;k++) {
		for (int q=1;q<=n;q++) {
			for (int w=1;w<=n;w++){
				if (q!=w&&w!=k&&q!=k)
				g[q][w]=min(g[q][k]+g[k][w],g[q][w]);
			}
		}
	}
	int sum=100000001,index;
	for (int q=1;q<=n;q++) {
		int ans=0;
		for (int w=1;w<=n;w++) {
			if (q!=w) if (g[q][w]!=INF) ans+=g[w][q];
		}
		if (ans<sum) {
			sum=ans;
			index=q;
		}
	}
//	ll maxl[MAXN]={0};
//	for (int w=1;w<=n;w++) {
//		for (int q=1;q<=n;q++) {
//			if (g[q][w]!=INF)
//			maxl[q]+=g[q][w];
//		}
//	}
//	ll maxx=-1,index=0;
//	for (int q=1;q<=n;q++) {
//		if (maxx<maxl[q]) {
//			maxx=maxl[q];
//			index=q;
//		}
//	}
	cout << index;
	//printf("%lld\n",index);
	return 0;
}