记录编号	518402	评测结果	AAAAA
题目名称	[HAOI 2005]希望小学	最终得分	100
用户昵称	Hale	是否通过	通过
代码语言	C++	运行时间	0.001 s
提交时间	2018-10-30 12:35:47	内存使用	0.32 MiB

#include<bits/stdc++.h>
using namespace std;
int vgy,vgx,vgz,vbx,vby,vbz;//x平路速度,y上坡速度,z下坡速度 
struct node
{ int d;
  int dist;
};
vector<node> g[31];
int numg[31],numb[31],d[31];
bool inque[31];
int k,p,n;
queue<int> que;
void spfa(int s)
{ memset(d,9999999,sizeof(d));
  memset(inque,0,sizeof(inque));
  d[s]=0;
  inque[s]=true;
  que.push(s);
  while (!que.empty())
  { int u=que.front();
    que.pop();
	inque[u]=false;
	for (int i=0;i<g[u].size();i++)
	{ int v=g[u][i].d;
	  int w=g[u][i].dist;
	  if (d[u]+w<d[v]) {d[v]=d[u]+w;
	                    if (!inque[v])
						{ que.push(v);
						  inque[v]=true;
						  }  
					   }
	 } 
  }
}
int main()
{ freopen("hopeschool.in","r",stdin);
  freopen("hopeschool.out","w",stdout);
  scanf("%d %d %d %d %d %d %d",&n,&vbx,&vby,&vbz,&vgx,&vgy,&vgz);
  for (int i=1;i<=n;i++) scanf("%d",&numb[i]);
  for (int i=1;i<=n;i++) scanf("%d",&numg[i]);
  scanf("%d",&k);
  for (int i=1;i<=k;i++)
  { int u,v;
    int  w1,w2,x,y,z;//x平路，y上坡，z下坡 
    scanf("%d%d%d%d%d",&u,&v,&x,&y,&z);
    w1=(x*vbx+y*vby+z*vbz)*numb[u]+(x*vgx+y*vgy+z*vgz)*numg[u];
    w2=(x*vbx+y*vbz+z*vby)*numb[v]+(x*vgx+y*vgz+z*vgy)*numg[v];
	g[u].push_back((node){v,w2});
    g[v].push_back((node){u,w1});
   }
  int k=0;
  double ans=522520;
  for (int i=1;i<=n;i++)
  { int pp=1;
    spfa(i);
    int  sum=0;
    for (int j=1;j<=n;j++)
    {if (d[j]!=9999999)sum+=d[j];
     else {pp=0;break;} 
	}
	if (pp=0) continue; 
	if (sum<ans) {ans=sum;k=i;}
  }
  printf("%d",k);
  return 0;  
}