http://www.cogs.pro/cogs/problem/problem.php?pid=21
★★ 输入文件：hopeschool.in 输出文件：hopeschool.out 简单对比
时间限制：1 s 内存限制：128 MB
【问题描述】
地处偏僻山区的X乡有N个自然村，目前还没有一所小学，孩子们要么不上学，要么需要翻过一座大山到别处上学。如今好啦，有一位热心人士准备捐款在某个自然村建立一所希望小学。
通过调查发现，X乡各个村庄之间的道路较为复杂，有平路、上坡和下坡。考虑到每个村孩子们的人数不同，走上坡、下坡和平路的速度也不同，?男孩和女孩走路速度也不同，请你为X乡选择一个最合适建立希望小学的村庄，使得所有的孩子花在路上的总时间最少。
【输入文件】
hopeschool.in
第1行： N B1 B2 B3 G1 G2 G3 (村庄数、男孩分别走平路、上坡、下坡每千米花费的时间以及女孩分别走平路、上坡、下坡每千米花费的时间)
第2行： Xl X2……Xn (Xi表示第i个村要上学的男孩人数)
第3行： Y1 Y2……Yn (Yi表示第i个村要上学的女孩人数)
第4行： K (道路数)
第5—K+4行： Ai Bi Si1 Si2 Si3 (村庄Ai到村庄Bi，平路Sil千米，上坡Si2千米，下坡Si3千米,i=1,2,…，K)
【输出文件】
hopeschool.out
T（将要建立希望小学村庄的编号）
【约束条件】
(1) N<=30， Xi<=20， Yi<=20
(2) K<=100， 每条路的长度<=30千米
(3) B1，B2，B3，G1，G2，G3为整数，都小于10个单位时间／每千米
(4) 每条道路只给出一组数据。例如：5 8 7 10 3表示从村庄5往村庄8走，平路
有7千米，上坡10千米。 下坡3千米；当然也表示从村庄8往村庄5走，平路有7千米，
上坡3千米。下坡10千米。
【输入输出样例】
hopeschool.in
2 2 2 1 2 3 2
10 12
5 4
1
1 2 10 2 1
hopeschool.out
2
注意约束条件（3），数据范围这么、、Floyed可以了
1 #include <algorithm> 2 #include <cstdio> 3 4 using namespace std; 5 6 const int INF(0x3f3f3f3f); 7 const int N(110); 8 9 inline void read(int &x) 10 { 11 x=0; register char ch=getchar(); 12 for(;ch>'9'||ch<'0';) ch=getchar(); 13 for(;ch>='0'&&ch<='9';ch=getchar()) x=x*10+ch-'0'; 14 } 15 16 int AC() 17 { 18 freopen("hopeschool.in","r",stdin); 19 freopen("hopeschool.out","w",stdout); 20 int n,k,b1,b2,b3,g1,g2,g3,dis[N][N],x[N],y[N]; 21 read(n),read(b1),read(b2),read(b3),read(g1),read(g2),read(g3); 22 for(register int i=1;i<=n;++i) 23 for(register int j=1;j<=n;++j) 24 dis[i][j]=INF*(i!=j); 25 for(register int i=1;i<=n;++i) read(x[i]); 26 for(register int i=1;i<=n;++i) read(y[i]); 27 read(k); 28 for(register int s1,s2,s3,a,b;k--;) 29 { 30 read(a),read(b),read(s1),read(s2),read(s3); 31 dis[a][b]=x[a]*(s1*b1+s2*b2+s3*b3)+y[a]*(s1*g1+s2*g2+s3*g3); 32 dis[b][a]=x[b]*(s1*b1+s2*b3+s3*b2)+y[b]*(s1*g1+s2*g3+s3*g2); 33 } 34 for(register int k=1;k<=n;++k) 35 for(register int i=1;i<=n;++i) 36 for(register int j=1;j<=n;++j) 37 if(dis[i][j]>dis[i][k]+dis[k][j]) 38 dis[i][j]=dis[i][k]+dis[k][j]; 39 int ans,sum,maxx=INF; 40 for(register int i=1;i<=n;++i) 41 { 42 sum=0; 43 for(register int j=1;j<=n;++j) 44 sum+=dis[j][i]; 45 if(sum<maxx) maxx=sum,ans=i; 46 } 47 printf("%d ",ans); 48 return 0; 49 } 50 51 int I_want_AC=AC(); 52 int main() {;}