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

· · 题解

不知道为什么有人说这题卡spfa

显然spfa跑得很快。

欢迎来hack

#include<bits/stdc++.h>
using namespace std;
#define MP make_pair
#define FI first
#define SE second
typedef long long LL;
typedef pair<int,int> PII;
int n,p,c,pos[508],a,b,d;
int nume,to[3008],nxt[3008],head[808],f[3008];
inline void addedge(int x,int y)
{
    ++nume;to[nume]=y;nxt[nume]=head[x];head[x]=nume;f[nume]=d;
}
queue<int> q;
int dis[808],ans=INT_MAX,tmp[808];
bool vis[808];
void dijk(int x)
{
    while(!q.empty())    q.pop();
    memset(vis,0,sizeof(vis));
    memset(dis,0x3f,sizeof(dis));
    dis[x]=0;
    q.push(x);
    vis[x]=1;
    while(!q.empty()){
        int now=q.front();q.pop();vis[now]=0;
        for(int i=head[now];i;i=nxt[i]){
            if(dis[to[i]]>dis[now]+f[i]){
                dis[to[i]]=dis[now]+f[i];
                if(!vis[to[i]]){
                    q.push(to[i]);
                    vis[to[i]]=1;
                }
            }
        }
    }
}
int main()
{
    cin>>n>>p>>c;
    for(int i=1;i<=n;i++){
        cin>>pos[i];
    }
    for(int i=1;i<=c;i++){
        cin>>a>>b>>d;
        addedge(a,b);
        addedge(b,a);
    }
    for(int i=1;i<=n;i++){
        dijk(pos[i]);
        for(int j=1;j<=p;j++){
            tmp[j]+=dis[j];
        }
    }
    for(int i=1;i<=p;i++){
        if(tmp[i]<ans)    ans=tmp[i];
    }
    cout<<ans;
    return 0;
}