洛谷P1828 香甜的黄油 Sweet Butter

客官°小女子只卖身不卖艺 2022-10-02 14:53 111阅读 0赞

### 香甜的黄油 Sweet Butter ###

黄油真的是这么做的吗？！！！\[惶恐\]  
这道题是Dijkstra算法的简单变形  
通过题意我们要找到一个点使奶牛所在点的路程和最短。通过Dijkstra的模板我们可以求的一点到其他任一点的最短路径，那么我们可以遍历所有点跑一边Dijkstra，每个点的最后把奶牛所在点的dis相加，最后将每个点的路程和进行比较，输出最短。  
AC代码如下：

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #include<queue>
    #include<vector>
    #define INF 0x3f3f3f3f
    #define MAXN 1000
    using namespace std;
    
    vector<int> G[MAXN];
    vector<int> M[MAXN];
    
    int cow[MAXN];
    int dis[MAXN];
    int done[MAXN];
    
    struct item
    {
        int u;
        int dis;
        friend bool operator < (struct item x,struct item y)
        {
            return x.dis>y.dis;
        }
    };
    
    priority_queue<item> q;
    int mn=INF;
    int main()
    {
        
        int n,p,c;
        scanf("%d%d%d",&n,&p,&c);
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&cow[i]);
        }
        for(int i=1;i<=c;i++)
        {
            int x,y,z;
            scanf("%d%d%d",&x,&y,&z);
            G[x].push_back(y);
            M[x].push_back(z);
            G[y].push_back(x);
            M[y].push_back(z);
        }
    
        for(int i=1;i<=p;i++)
        {
            memset(dis,0x3f,sizeof(dis));
            memset(done,0,sizeof(done));
            q.push((item){i,0});
            dis[i]=0;
            while(!q.empty())
            {
                item r;
                r=q.top();
                q.pop();
                int au=r.u;
                if(done[au]) continue;
                done[au]=1;
                for(int j=0;j<G[au].size();j++)
                {
                    int p=G[au][j];
                    int c=dis[au]+M[au][j];
                    if(dis[p]>c)
                    {
                        dis[p]=c;
                        q.push((item){p,c});
                    }
                }
            }
            int total=0;
            for(int j=1;j<=n;j++)
            {
                if(cow[j]==INF) continue;
                total=total+dis[cow[j]];
            }
            mn=min(mn,total);
       }
        printf("%d",mn);
        return 0;
    }

转载于:https://www.cnblogs.com/LITTLESUNwl/p/10757313.html