记录编号	577517	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	HeSn	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2022-11-07 22:14:44	内存使用	0.00 MiB

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, m, spd[5][5], a[50], b[50], g[2][50][50], ans, num;
signed main() {
	freopen("hopeschool.in", "r", stdin);
	freopen("hopeschool.out", "w", stdout);
	cin >> n >> spd[1][1] >> spd[1][2] >> spd[1][3] >> spd[2][1] >> spd[2][2] >> spd[2][3];
	for(int i = 1; i <= n; i ++) {
		cin >> a[i];
	}
	for(int i = 1; i <= n; i ++) {
		cin >> b[i];
	}
	cin >> m;
	memset(g, 0x3f, sizeof(g));
	for(int i = 1; i <= m; i ++) {
		int x, y, s1, s2, s3;
		cin >> x >> y >> s1 >> s2 >> s3;
		g[0][x][y] = a[x] * s1 * spd[1][1] + a[x] * s2 * spd[1][2] + a[x] * s3 * spd[1][3];
		g[1][x][y] = b[x] * s1 * spd[2][1] + b[x] * s2 * spd[2][2] + b[x] * s3 * spd[2][3];
		
		g[0][y][x] = a[y] * s1 * spd[1][1] + a[y] * s3 * spd[1][2] + a[y] * s2 * spd[1][3];
		g[1][y][x] = b[y] * s1 * spd[2][1] + b[y] * s3 * spd[2][2] + b[y] * s2 * spd[2][3];
	}
	for(int i = 1; i <= n; i ++) {
		g[0][i][i] = g[1][i][i] = 0;
	}
	for(int k = 1; k <= n; k ++) {
		for(int i = 1; i <= n; i ++) {
			for(int j = 1; j <= n; j ++) {
				g[0][i][j] = min(g[0][i][j], g[0][i][k] + g[0][k][j]);
				g[1][i][j] = min(g[1][i][j], g[1][i][k] + g[1][k][j]);
			}
		}
	}
	ans = 1e8;
	for(int i = 1; i <= n; i ++) {
		int sum = 0;
		for(int j = 1; j <= n; j ++) {
			sum += g[0][j][i] + g[1][j][i];
		}
		if(sum < ans) {
			ans = sum;
			num = i;
		}
	}
	cout << num;
	return 0;
}