记录编号	422553	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	@@@	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2017-07-09 20:59:21	内存使用	0.32 MiB

#include <fstream>
#include <vector>
#include <queue>
#ifndef inf
#define inf 99999999
#endif
using namespace std;
ifstream cin("hopeschool.in");
ofstream cout("hopeschool.out");
int  n ,B_, B_up, B_down, G_, G_up, G_down;
int K;
int e1[31][31],e2[31][31];
class V
{
public:
	int boy,girl;
	
	
}v[31];
int cyf()
{
	int i,j;
	cin >> n >> B_ >> B_up >> B_down >> G_ >> G_up >> G_down;
	 for(i=1;i <= n;i++)   
	 {
		for(j=1;j <= n;j++)   
		{
			//if(i==j)
			// 	e2[i][j] = e1[i][j] = 0;   
			//else
			 	e2[i][j] = e1[i][j] = inf; 
		} 
	}
	
	for (i = 1; i <= n; ++i)
	{
		cin >> v[i].boy;
		/* code */
	}
	for (i = 1; i <= n; ++i)
	{
		cin >> v[i].girl;
		/* code */
	}
	cin >> K;
	for (i = 1; i <= K; ++i)
	{
		int a,b,s_,s_up,s_down;
		cin >> a >> b >> s_ >> s_up >> s_down;
		e1[a][b] = v[a].boy*(s_*B_ + s_up*B_up + s_down*B_down);//boy  ->
		e1[b][a] = v[b].boy*(s_*B_ + s_up*B_down + s_down*B_up);//boy  <-
		e2[a][b] = v[a].girl*(s_*G_ + s_up*G_up + s_down*G_down);//girl ->
		e2[b][a] = v[b].girl*(s_*G_ + s_up*G_down + s_down*G_up);//girl <-
	}
	
	for (int k = 1; k <= n; ++k)
	{
		for (int i = 1; i <= n; ++i)
		{
			for (int j = 1; j <= n; ++j)
			{
				if (e1[i][j] > e1[i][k]+e1[k][j])
				{
					e1[i][j] = e1[i][k]+e1[k][j];
					
				}
				if (e2[i][j] > e2[i][k]+e2[k][j])
				{
					e2[i][j] = e2[i][k]+e2[k][j];
					
				}
			}
			
		}
		
	}
	

	int ans,mi = inf,jj;
	for (int i = 1; i <= n; ++i)
	{
		ans = 0;
		for (int j = 1; j <= n; ++j)
		{
			if (i != j)
			{
				ans += e1[j][i]+e2[j][i];
				/* code */
			}
			
		}
		if (ans < mi)
			{
				mi = ans;
				jj = i;
				/* code */
			}
		
	}
	cout << jj << endl;
	/*
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if(e1[i][j] == inf)
				cout << 'x' << ' ';
			else
			cout <<e1[i][j] << ' ';
			
		}
		cout << endl;
		
	}
	cout << endl;
	for (int i = 1; i <= n; ++i)
	{
		for (int j = 1; j <= n; ++j)
		{
			if(e2[i][j] == inf)
				cout << 'x' << ' ';
			else
			cout <<e2[i][j] << ' ';
			
		}
		cout << endl;
		
	}
	*/
	cin.close();				
	cout.close();
		return 0;
}
int hhhh = cyf();
int main() {;}