首页 > 代码库 > 21. [HAOI2005] 希望小学 (wa1)

21. [HAOI2005] 希望小学 (wa1)

★★   输入文件: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 2 10 2 1

hopeschool.out

2

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
 
using namespace std;
const int N=35;
const int Maxn=9999999;
 
int map[N][N];
int boy[N],girl[N]; 
int n,bmid,bup,bdown,gmid,gup,gdown,road;
int u,v,mid,up,down;
int ans_dis=Maxn,answer,now_dis;
 
inline int read()
{
    int x=0;char c=getchar();
    while(c<0||c>9)c=getchar();
    while(c>=0&&c<=9)x=x*10+c-0,c=getchar();
    return x;
}
 
int main()
{
    freopen("hopeschool.in","r",stdin);
    freopen("hopeschool.out","w",stdout);

    n=read(),bmid=read(),bup=read(),bdown=read(),
    gmid=read(),gup=read(),gdown=read();
    
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            map[i][j]=Maxn;
            
    for(int i=1;i<=n;i++)
        boy[i]=read();
    for(int i=1;i<=n;i++)
        girl[i]=read();
        
    road=read();
    for(int i=1;i<=road;i++)
    {
        u=read(),v=read(),mid=read(),up=read(),down=read();
        int impb=bmid*mid+bup*up+bdown*down;
        int impg=gmid*mid+gup*up+gdown*down;
        map[u][v]=boy[u]*(impb)+girl[u]*(impg);
        map[v][u]=boy[v]*(impb)+girl[v]*(impg);          
    }
    
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                map[i][j]=min(map[i][j],map[i][k]+map[k][j]);
    
    for(int i=1;i<=n;i++)
    {
        now_dis=0;
        for(int j=1;j<=n;j++)
            if((i-j)!=0)
                now_dis+=map[j][i];
        if(now_dis<ans_dis)
            ans_dis=now_dis,
            answer=i;
    }
    printf("%d%d",answer,ans_dis);
    return 0;
}
/*
8 2 3 1 3 4 2
10 10 10 10 10 10 10 10
2 2 2 2 2 2 2 2
11
1 2 4 2 2
2 3 5 1 3
3 4 6 0 0
4 5 3 5 2
5 6 9 0 1
6 7 8 2 0
7 1 5 2 2
1 8 0 5 0
7 8 0 5 0
3 8 2 5 0
4 8 0 6 0
*/

 

21. [HAOI2005] 希望小学 (wa1)