信息学奥赛一本通 1345：【例4-6】香甜的黄油第四章图论

长春高老师编程

765人浏览 · 2024-04-06 10:36:44

长春高老师编程 · 2024-04-06 10:36:44 发布

1345：【例4-6】香甜的黄油

时间限制: 1000 ms 内存限制: 65536 KB

【题目描述】

农夫John发现做出全威斯康辛州最甜的黄油的方法：糖。把糖放在一片牧场上，他知道N（1≤N≤500）只奶牛会过来舔它，这样就能做出能卖好价钱的超甜黄油。当然，他将付出额外的费用在奶牛上。

农夫John很狡猾。像以前的巴甫洛夫，他知道他可以训练这些奶牛，让它们在听到铃声时去一个特定的牧场。他打算将糖放在那里然后下午发出铃声，以至他可以在晚上挤奶。

农夫John知道每只奶牛都在各自喜欢的牧场（一个牧场不一定只有一头牛）。给出各头牛在的牧场和牧场间的路线，找出使所有牛到达的路程和最短的牧场（他将把糖放在那）。

【输入】

第一行: 三个数：奶牛数N，牧场数P（2≤P≤800），牧场间道路数C(1≤C≤1450)。

第二行到第N+1行: 1到N头奶牛所在的牧场号。

第N+2行到第N+C+1行：每行有三个数：相连的牧场A、B，两牧场间距（1≤D≤255），当然，连接是双向的。

【输出】

一行输出奶牛必须行走的最小的距离和。

【输入样例】

【输出样例】

【提示】

说明：放在4号牧场最优。

解析：枚举放糖的牧场，使用福特算法，计算单源（放糖的牧场）最短路径，求出路径和。

详见代码：

#include <bits/stdc++.h>
using namespace std;
//福特（Ford）算法求单源最短路径
int N,P,C;
int niu[505];//牛在哪个牧场
int d[805][805];//牧场间距离
int dis[805];
bool b[805];//是否入队
vector <int> bian[805];//邻接表存边
queue <int> q;
int ans=1e9;
int main() {
    cin>>N>>P>>C;
    for(int i=1;i<=N;i++){//输入牛的位置
        cin>>niu[i];
    }
    for(int i=1;i<=C;i++){//输入边及边长
        int x,y,z;
        cin>>x>>y>>z;
        bian[x].push_back(y);
        bian[y].push_back(x);
        d[x][y]=d[y][x]=z;
    }
    for(int i=1;i<=P;i++){//枚举每个牧场放糖
        //初始化最小值为无穷大
        memset(dis,0x3f,sizeof(dis));
        dis[i]=0;
        b[i]=1;
        q.push(i);//起点入队
        while(!q.empty()){//队列中每个点
            int t=q.front();
            q.pop();
            b[t]=0;//标记出队
            for(int j=0;j<bian[t].size();j++){//枚举边
                int p=bian[t][j];//目标点
                if (dis[p]>dis[t]+d[t][p]){//更新最小路径长度
                    dis[p]=dis[t]+d[t][p];
                    if (b[p]==0){//被更新的点入队
                        b[p]=1;
                        q.push(p);
                    }
                }
            }
        }
        int sum=0;
        for(int j=1;j<=N;j++){//计算路径和
            sum+=dis[niu[j]];
        }
        ans=min(ans,sum);//求最小值
    }
    cout<<ans;
    return 0;
}