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

· · 题解

已经有dalao用SPFA做出来拉，不过讲的有点不详细在此细讲一下。

这道题一瞅就知道应该是一个最短路

再讲SPFA之前提供一个70分做法

裸的djkstra

#include<bits/stdc++.h>
using namespace std;
const int maxn=3000+10;
int g[maxn],n,m,d[maxn][maxn],to[maxn],cnt,first[maxn],p1,p[maxn],next[maxn],piao[maxn];
int w[maxn],dis[maxn];
/*void add(int u,int v,int l){
    ++cnt;
    to[cnt]=v;  
    next[cnt]=first[u];
    first[u]=cnt;   
    w[cnt]=l;
}*/
void dijkstra(int s){
    for(int i=1;i<=n;i++)dis[i]=10000;
    memset(piao,0,sizeof(piao));
    int u;
    int minn;
    for(int i=1;i<=n;i++)
        dis[i]=d[s][i];
    piao[s]=1;
    dis[s]=0;
    for(int i=2;i<=n;i++){
        minn=2147483647-1;
    for(int j=1;j<=n;j++)
        if(piao[j]==0&&dis[j]<minn)
            minn=dis[j],u=j;
    piao[u]=1;
    for(int j=1;j<=n;j++)
        if(dis[j]>dis[u]+d[u][j]&&!piao[j])
            dis[j]=dis[u]+d[u][j];
            }
        }

int main(){
    cin>>p1>>n>>m;
    memset(d,0x3f3f,sizeof(d));
    for(int i=1;i<=p1;i++)
    scanf("%d",&g[i]);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        d[x][y]=d[y][x]=z;
    }
    int minn=100000000;
    for(int i=1;i<=n;i++){
        dijkstra(i);
        int ans=0;
        for(int j=1;j<=p1;j++)
        ans+=dis[g[j]];
        minn=min(minn,ans);
    //  cout<<ans<<endl;
    }
    cout<<minn<<endl;
    return 0;
    }

很显然会T掉

不过有人问了为什么不直接写SPFA

because SPFA 他死了，在非特殊情况下（有负权）建议用dijkstra，比如归程，用SPFA会被卡到60分的

接下来总算到了介绍SPFA了

段凡丁论文中的复杂度证明 (O(kE)（这么好的时间复杂度？），k 是小常数)是错误的，在此略去。该算法的最坏复杂度为 O(VE)（都退化成Bellman—Ford了）

SPFA是在 Bellman-Ford 算法上的队列优化，所以学习前先看一下Bellman-Ford。

1,.初始化:将除源点外的所有顶点的最短距离估计值 d[v] -->+∞, d[s]-->0;

2.迭代求解:反复对边集E中的每条边进行松弛操作，使得顶点集V中的每个顶点v的最短距离估计值逐步逼近其最短距离;(运行|v|-1次)

3.检验负权回路:判断边集E中的每一条边的两个端点是否收敛。如果存在未收敛的顶点，则算法返回false，表明问题无解;否则算法返回true，并且从源点可达的顶点v的最短距离保存在 d[v]中。

摘自百度。

我们注意一下迭代求解的部分，我们发现Bellman-Ford是将每一条边进行了relax操作，这样就会出现很多毫无意义的操作，所以能不能优化一下呢？

实际上我们松弛是只要松弛 当前点的最短路径估计值对离开当前点所指向的结点进行松弛操作，就行了。这当中就需要用队列来存储所指的点就行了，所以主要代码就出来了

for(int i=first[u];i;i=next[i]){//因为SPFA是以边为对象所以可以采用邻接表来存储
            int v=to[i];
            if(d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
             //   cout<<v<<" "<<d[v]<<endl;
                if(!p[v]){
                    q.push(v);
                    p[v]=1;
                }           
            }

再附上邻接表代码

void add(int u,int v,int l){
    ++cnt;
    to[cnt]=v;  
    next[cnt]=first[u];
    first[u]=cnt;   
    w[cnt]=l;
}

把这些给想明白了，代码就很简单了。附上代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=30000+10;
int g[maxn],n,m,d[maxn],to[maxn],cnt,first[maxn],p1,p[maxn],next[maxn];
int w[maxn],dis[maxn];
queue<int>q;
void add(int u,int v,int l){
    ++cnt;
    to[cnt]=v;  
    next[cnt]=first[u];
    first[u]=cnt;   
    w[cnt]=l;
}
void spfa(int s){
    memset(p,0,sizeof(p));
    for(int i=1;i<=n;i++)d[i]=10000;
    d[s]=0; q.push(s);p[s]=1;
    while(!q.empty()){
        int u=q.front();
        q.pop();
        p[u]=0;
        for(int i=first[u];i;i=next[i]){
            int v=to[i];
            if(d[v]>d[u]+w[i]){
                d[v]=d[u]+w[i];
             //   cout<<v<<" "<<d[v]<<endl;
                if(!p[v]){
                    q.push(v);
                    p[v]=1;
                }           
            }   
        }
    }
    }
int main(){
    cin>>p1>>n>>m;
    for(int i=1;i<=p1;i++)
    scanf("%d",&g[i]);
    for(int i=1;i<=m;i++){
        int x,y,z;
        cin>>x>>y>>z;
        add(x,y,z);
        add(y,x,z);
    }
    int minn=100000000;
    for(int i=1;i<=n;i++){//和SPFA模板不一样的就是需要对每个点进行SPFA
        spfa(i);
        int ans=0;
        for(int j=1;j<=p1;j++)
        ans+=d[g[j]];
        minn=min(minn,ans);
    //  cout<<ans<<endl;
    }
    cout<<minn<<endl;
    return 0;//完结散花
    }

最后在提一句，SPFA之所以可以判负环，是因为是以边为对象。所以判负环时。只要看一下一个点还能不能再进行松弛操作。这样就可以判断负环了，具体代码就不放出来了自己想一想

谢谢管理员大大审核此篇题解，如有不足请指正。

可以点个赞吗？