题解 P1828 【香甜的黄油 Sweet Butter】

leozhudd · 2017-08-07 00:29:56 · 题解

其实就是一个裸的SPFA

用vector模拟邻接表来存图

然后对每个牧场当成起点做一次SPFA，每次统计更新最小值就ok；

【C++】

#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
using namespace std;
const int N=900;
const int M=1500;
int n,m;
vector< pair<int,int> >node[N];        //用VECTOR模拟邻接表 
queue<int>Q;
bool book[N];    //记录哪些点在当前队列里 
int dis[N];        
int cow[502];    //每个牧场有多少牛 
int main()
{
    int i,j,k; 
    int start;
    int ans=999999999;
    int u,v,len;
    int cow_num;
    cin>>cow_num>>n>>m;    //n个点，m条边
    for(i=1;i<=cow_num;i++)
    {
        int tmp;
        cin>>tmp;
        cow[tmp]++;
    }
    for(i=1;i<=m;i++)
    {
        cin>>u>>v>>len;
        node[u].push_back( make_pair(v,len) );    //因为是无向图，所以正反都存一遍 
        node[v].push_back( make_pair(u,len) );
    }
    for(start=1;start<=n;start++)        //对每个牧场做一次SPFA，枚举起点start 
    {
        memset(dis,0x3f,sizeof(dis));    //初始化 
        memset(book,0,sizeof(book));    //初始化 
        dis[start]=0;
        book[start]=1;        //标记起点入队 
        Q.push(start);        //起点先入队
        while(!Q.empty())
        {
            u=Q.front();
            Q.pop();
            book[u]=0;        //标记u点出队 
            for(i=0;i<node[u].size();i++)
            {
                v=node[u][i].first;
                len=node[u][i].second;
                if( dis[v]>dis[u]+len )
                {
                    dis[v]=dis[u]+len;
                    if(book[v]==0)
                    {
                        book[v]=1;        //标记v点入队 
                        Q.push(v);
                    }
                }
            }    
        }
        int now=0;
        for(i=1;i<=n;i++)
            if(i!=start)
                now+=cow[i]*dis[i];        //统计当前起点的总距离和 
        ans=min(ans,now);    //每次更新最小值 
    }
    cout<<ans;
    return 0;
}