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

· · 题解

可以使用Heap优化的Dijkstra算法

在C++中，可以利用priority_queue来实现Heap的功能


#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<queue>
#define maxn 805
#define INF 0x7fffffff
using namespace std;
struct Edge{
    int from,to,dist;
};
vector<Edge> G[maxn];
int a[maxn],d[maxn];
bool vis[maxn];
typedef pair<int,int> pii;
priority_queue<pii,vector<pii>,greater<pii> > Q;//优先队列
int main()
{
    int n,p,c,i,x,y,z,u,j,sum=0,ans=INF;
    pii w;
    scanf("%d%d%d",&n,&p,&c);
    memset(a,0,sizeof(a));
    for(i=0;i<n;i++)
    {
        scanf("%d",&x);
        a[x]++;
    }
    for(i=1;i<=n;i++)
        G[i].clear();
    for(i=0;i<c;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        G[x].push_back((Edge){x,y,z});
        G[y].push_back((Edge){y,x,z});//注意到边是双向的
    }
    for(i=1;i<=p;i++)
    {
        memset(d,0x3f,sizeof(d));
        memset(vis,0,sizeof(vis));
        d[i]=0;
        Q.push(make_pair(0,i));
        while(!Q.empty())
        {
            u=Q.top().second;
            Q.pop();
            if(vis[u])continue;
            vis[u]=1;
            for(j=0;j<G[u].size();j++)
            {
                Edge &e=G[u][j];
                if(d[e.to]>d[u]+e.dist)
                {
                    d[e.to]=d[u]+e.dist;
                    Q.push(make_pair(d[e.to],e.to));//插入
                }
            }
        }
        sum=0;
        for(j=1;j<=p;j++)
            sum+=d[j]*a[j];
        ans=min(ans,sum);
    }
    printf("%d",ans);//输出答案
    return 0;
}