21. [HAOI2005] 希望小学

★★ 输入文件：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

Floyd算法、、、

（开始时读错题了、、、、村庄数、男孩分别走平路、上坡、下坡每千米花费的时间以及女孩分别走平路、上坡、下坡每千米花费的时间）竟然硬是看成了速度、、、、（ORZ）

代码：

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define N 100
#define maxn 9999999
using namespace std;
bool vis[N][N];
double t1,t2,sum,maxx=maxn;
int n,k,x,y,s1,s2,s3,vb1,vb2,vb3,vg1,vg2,vg3,ans,sb[N],sg[N];
struct Dis
{
    double tim;
    int up,down,flat;
}dis[N][N];
int read()
{
    ,f=;char ch=getchar();
    ; ch=getchar();}
    +ch-'; ch=getchar();}
    return x*f;
}
int main()
{
    freopen("hopeschool.in","r",stdin);
    freopen("hopeschool.out","w",stdout);
    n=read(),vb1=read(),vb2=read(),vb3=read();
    vg1=read(),vg2=read(),vg3=read();
    ;i<=n;i++) sb[i]=read();
    ;i<=n;i++) sg[i]=read();
    k=read();
    ;i<=n;i++)
        ;j<=n;j++)
            dis[i][j].tim=(i!=j)*maxn;
    ;i<=k;i++)
    {
        x=read(),y=read(),s1=read(),s2=read(),s3=read();
        dis[x][y].tim=sb[x]*(vb1*s1+vb2*s2+vb3*s3)+sg[x]*(vg1*s1+vg2*s2+vg3*s3);
        dis[y][x].tim=sb[y]*(vb1*s1+vb2*s3+vb3*s2)+sg[y]*(vg1*s1+vg2*s3+vg3*s2);
    }
    ;k<=n;k++)
     ;i<=n;i++)
      ;j<=n;j++)
       if(dis[i][j].tim>dis[i][k].tim+dis[k][j].tim)
        dis[i][j].tim=dis[i][k].tim+dis[k][j].tim;
    ;i<=n;i++)
    {
        sum=;
        ;j<=n;j++)
         sum+=dis[j][i].tim;
        if(sum<maxx) maxx=sum,ans=i;
     }
    printf("%d",ans);
}

巴特西

cogs——21. [HAOI2005] 希望小学