记录编号	581181	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-07-30 20:48:15	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
const int N = 110,M = 310;
int n,m,b1,b2,b3,g1,g2,g3;
int b[N],g[N];
struct node{
	int st,up,dn;
};//存边的平路,上坡,下坡长度千米 
struct made{
	int ver,nx;
	node ed;
}e[M];//链式前项星，邻接表 
int hd[N],v[N],d[N],ds[N][N],tot,ans = INT_MAX,s1;
void add_(int x,int y,node z){
	tot++;
	e[tot].ver = y,e[tot].ed = z,e[tot].nx = hd[x],hd[x] = tot;
}//建图 
void init(){
	scanf("%d%d%d%d%d%d%d",&n,&b1,&b2,&b3,&g1,&g2,&g3);
	for(int i = 1;i <= n;i++)scanf("%d",&b[i]);
	for(int i = 1;i <= n;i++)scanf("%d",&g[i]);
	scanf("%d",&m);//麻烦输入┭┮﹏┭┮ 
	for(int i = 1;i <= m;i++){
		int x,y;node z,zz;
		scanf("%d%d%d%d%d",&x,&y,&z.st,&z.up,&z.dn);
		zz.st = z.st,zz.up = z.dn,zz.dn = z.up;
		add_(x,y,z);
		add_(y,x,zz);//双向存边，注意x到y的上坡是y到x的下坡 
	}
}
int time_(int x,node z){
	return b[x] * b1 * z.st + b[x] * b2 * z.up + b[x] * b3 * z.dn + g[x] * g1 * z.st + g[x] * g2 * z.up + g[x] * g3 * z.dn;
}//算第x个城市走z的道路 
void spfa(int x){
	memset(v,0,sizeof(v));
	for(int i = 1;i <= n;i++)d[i] = INT_MAX;
	queue<int>q;
	d[x] = 0,v[x] = 1;
	q.push(x);
	while(!q.empty()){
		int x = q.front();q.pop();
		v[x] = 0;
		for(int i = hd[x];i;i = e[i].nx){
			int y = e[i].ver;node z = e[i].ed;
			int su = time_(x,z);//算第x个城市走z的道路 
			if(d[x] + su < d[y]){
				d[y] = d[x] + su;
				if(!v[y])q.push(y),v[y] = 1;
			}
			
		}
	}
}//spfa求最短路 
int main(){
	freopen("hopeschool.in","r",stdin);
	freopen("hopeschool.out","w",stdout);
	init();
	for(int i = 1;i <= n;i++){
		spfa(i);
		for(int j = 1;j <= n;j++)
			ds[i][j] = d[j];//存i到j的最短路 
	}
	for(int i = 1;i <= n;i++){
		int s = 0;
		for(int j = 1;j <= n;j++)
		    s += ds[j][i];//因为是单向边，如果选第i个村子，必须是从j到i 
		if(s < ans)
			ans = s,s1 = i;
	}
	printf("%d\n",s1);
	
	return 0;
	
}