[圖論][最短路]HAOI：希望小學 hopeschool 解題報告

【問題描述】

地處偏僻山區的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

【分析】 

最短路問題，由於節點很少，而且還是多源最短路，所以Floyd算法很合適。

 由於男孩、女孩的速度不一樣，所以要分開求最短路。最後枚舉每個村莊求最優解即可。

【我的代碼】

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;

class Village
{
public:
    int s,e;
    int ping,up,down;
}V[203];
   
int Boy[31];
int Girl[31];
int Matb[31][31];
int Matg[31][31];
int N,K;
int B1,B2,B3;
int G1,G2,G3;

void init()
{
    scanf("%d %d %d %d %d %d %d\n",&N,&B1,&B2,&B3,&G1,&G2,&G3);
   
    for(int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            Matb[i][j]=-1,Matg[i][j]=-1;
   
    for (int i=1;i<=N;i++)
        Matg[i][i]=0,Matb[i][i]=0;
       
    for (int i=1;i<=N;i++)
        scanf("%d",&Boy[i]);
    for (int i=1;i<=N;i++)
        scanf("%d",&Girl[i]);
    scanf("%d\n",&K);
   
    for (int i=1;i<=K;i++)
    {
        scanf("%d %d %d %d %d\n",&V[i].s,&V[i].e,&V[i].ping,&V[i].up,&V[i].down);
        V[i+K].e=V[i].s;
        V[i+K].s=V[i].e;
        V[i+K].ping=V[i].ping;
        V[i+K].up=V[i].down;
        V[i+K].down=V[i].up;
    }
   
    int s,e;
    int t1;//人數
    int t2;//速度
    int t3;//路程
    int t4;//時間
    int t;//總時間
    for (int i=1;i<=K*2;i++)
    {
        t=0;
        s=V[i].s;
        e=V[i].e;
        t1=Boy[s];
        t2=B1;
        t3=V[i].ping;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=B2;
        t3=V[i].up;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=B3;
        t3=V[i].down;
        t4=t1*t3*t2;
        t+=t4;
        Matb[s][e]=t;
       
        t=0;
        t1=Girl[s];
        t2=G1;
        t3=V[i].ping;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=G2;
        t3=V[i].up;
        t4=t1*t3*t2;
        t+=t4;
       
        t2=G3;
        t3=V[i].down;
        t4=t1*t3*t2;
        t+=t4;
        Matg[s][e]=t;
    }
}
void Floydb()
{
    int temp;
    for (int k=1;k<=N;k++) 
    { 
        for(int i=1;i<=N;i++) 
        { 
            for(int j=1;j<=N;j++) 
            { 
                if ( Matb[i][k]!=-1 && Matb[k][j]!=-1) 
                { 
                    temp=Matb[i][k]+Matb[k][j];
                    if ( (Matb[i][j]==-1) || ( Matb[i][j]>temp ) ) 
                        Matb[i][j]=temp; 
                } 
            } 
        } 
    } 
}

void Floydg()
{
    int temp;
    for (int k=1;k<=N;k++) 
    { 
        for(int i=1;i<=N;i++) 
        { 
            for(int j=1;j<=N;j++) 
            { 
                if ( Matg[i][k]!=-1 && Matg[k][j]!=-1) 
                { 
                    temp=Matg[i][k]+Matg[k][j];
                    if ( (Matg[i][j]==-1) || ( Matg[i][j]>temp ) ) 
                        Matg[i][j]=temp; 
                } 
            } 
        } 
    } 
}

void Search()
{
    int Minn=200000000;
    int Minx=0;
    for (int i=1;i<=N;i++)
    {
        int t=0;
        for (int j=1;j<=N;j++)
            t=t+Matg[j][i]+Matb[j][i];
        if(t<Minn)
        {
            Minn=t;
            Minx=i;
        }
    }
    printf("%d\n",Minx);
}

int main()
{
    freopen("hopeschool.in","r",stdin);
    freopen("hopeschool.out","w",stdout);
    init();
    Floydb();
    Floydg();
    Search();
    return 0;
}

【評測結果】

正在连接评测机...

已连接到评测机

GRID	1
名称	Flitty
系统版本	1.00
备注	COGS 1号评测机 Flitty

正在编译...
编译成功

测试点	结果	得分	运行时间	内存使用	退出代码
1	正确	20	0.000 s	284 KB	0
2	正确	20	0.000 s	284 KB	0
3	正确	20	0.000 s	284 KB	0
4	正确	20	0.000 s	284 KB	0
5	正确	20	0.001 s	284 KB	0

运行完成
运行时间 0.002 s
平均内存使用 284 KB
测试点通过状况 AAAAA
得分：100
恭喜你通过了全部测试点!