香甜的黄油

张亦弛 · 2018-05-01 23:07:05 · 题解

题目较简单，直接上代码，附有注释（应该比较好懂）

#include<bits/stdc++.h>
using namespace std;
int n,p,c;
int fild;//奶牛所在牧场
int d[1455][1455]; //记录距离 
int t1,t2,t3;
int num[805];
int minn=999999999;//记录最终答案 
int ans;
int main()
{
    cin>>n>>p>>c;//奶牛数、牧场数、道路数 
    for(int i=1;i<=n;i++)
    {
        cin>>fild;
        num[fild]++;//fild牧场的奶牛数 
    }
    for(int i=1;i<=c;i++)
        for(int j=1;j<=c;j++)
            d[i][j]=999999999;//初始化距离 
    for(int i=1;i<=c;i++)
    {
        cin>>t1>>t2>>t3;
        d[t1][t2]=t3;
        d[t2][t1]=t3;//双向图，两边都要存 
    }
    for(int i=1;i<=p;i++)
        d[i][i]=0;//双向图 
    for(int k=1;k<=p;k++)
        for(int i=1;i<=p;i++)
            for(int j=1;j<=i;j++)//这个i非常重要 ，因为是双向的，只用算一半就好了 
                if(d[i][j]>d[i][k]+d[k][j])
                {
                    d[i][j]=d[i][k]+d[k][j];
                    d[j][i]=d[i][j];//双向图 
                }
    for(int i=1;i<=p;i++)
    {
        ans=0;//记得每次刷新ans 
        for(int j=1;j<=p;j++)
            ans+=(d[i][j]*num[j]);//计算总路程 
        if(ans<minn)
            minn=ans;//刷新最小值 
    }
    cout<<minn;//输出答案 
    return 0;//程序拜拜 
}