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

· · 题解

9012年了，spfa已经noip了，我们还是用dijkstra+堆优化吧！

做法：在一开始时统计每个牧场牛的个数，枚举放黄油的牧场，然后做p遍dijkstra，最后统计每个点的贡献，即为：该点到枚举点的最短路\times该点有牛的个数，最后取每个枚举点的最小值，就做完了。dijktra每次O(p\log p)，还有枚举点的O(p),所以总时间复杂度O(p^2\log p)。

dijkstra的模板可以去 P4779 看，这里就不再多说

Code: 
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline int read(){//快读
    register int x=0,v=1,ch=getchar();
    while(!isdigit(ch)){if(ch=='-')v=-1;ch=getchar();}
    while(isdigit(ch)){x=(x<<3)+(x<<1)+(ch^'0');ch=getchar();}
    return x*v;
}
const int MAX=1455,N=805;
struct E{//链式前向星存图
    int e,next,w;
}e[MAX<<1];
int head[N],cnt=1; 
inline void add(int u,int v,int w){
    e[cnt]=(E){v,head[u],w};
    head[u]=cnt++;
}
int n,c,p,s[N];
struct Node{
    int dis,pos;
    bool operator < (const Node&x)const{
        return x.dis<dis;
    }
};
int d[N],vis[N];
priority_queue<Node>q;
inline void dijkstra(int s){//dijkstra
    memset(d,0x3f3f3f3f,sizeof(d));
    memset(vis,0,sizeof(vis));
    d[s]=0;
    q.push((Node){0,s});
    while(!q.empty()){
        Node tmp=q.top();
        int x=tmp.pos;
        q.pop();
        if(vis[x])continue;
        vis[x]=1;
        for(register int i=head[x];i;i=e[i].next){
            int y=e[i].e;
            if(d[y]>d[x]+e[i].w){
                d[y]=d[x]+e[i].w;
                if(!vis[y])q.push((Node){d[y],y});
            }
        }
    }
}
int u,v,w,Sum,Ans=0x3f3f3f3f;
int main(){
    n=read();p=read();c=read();
    for(register int i=1;i<=n;++i){
        ++s[read()];//即为统计每个牧场拥有的牛的个数
    } 
    for(register int i=1;i<=c;++i){
        u=read(),v=read(),w=read();
        add(u,v,w);add(v,u,w);
    }
    for(register int i=1;i<=p;++i){//枚举
        dijkstra(i);
        Sum=0;
        for(register int j=1;j<=p;++j){
            Sum+=s[j]*d[j];//每个点对答案的贡献
        }
        Ans=Ans<Sum?Ans:Sum;//取最小值
    }
    printf("%d\n",Ans);//输出答案
    return 0;
}