首页 > 其他 > 详细

图论最短路——spfa

时间:2018-09-25 17:15:53      阅读:159      评论:0      收藏:0      [点我收藏+]

今天开始图论的最短路的最后复习,今天自己手打spfa虽然看了一眼书,但是也算是自己打出来的,毕竟很久没打了,而且还是一遍a代码下来15min左右就搞完了,成就感++。所以呢来篇博客记录一下。

技术分享图片

香甜的黄油,当年做的时候吃了不少苦头现在完全会打了,下面是当时我的代码:

技术分享图片
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<cmath>
#include<ctime>
#include<iostream>
#include<string>
using namespace std;
const int maxn=1002,inf=1000000000;
int n,p,c,a,b,d,t,dist[maxn],s1[maxn],inq[maxn];
vector<int>g[maxn],w[maxn];
        
void spfa(int s)
{
    queue<int>a;//一个队列a
    for(int i=1;i<=p;i++)//循环4个牧场都附极大值
    dist[i]=inf;
    memset(inq,0,sizeof(inq));//清空inp

    dist[s]=0;//把到当前的牧场距离设为0,毕竟是自己到自己
    a.push(s);//进队
    inq[s]=1;//使其为1

    while(!a.empty())//如果队列不为空
    {
        int i=a.front();//返回队首元素
        a.pop();//弹出队首
        inq[i]=0;//使其为0
        for(int k=0;k<g[i].size();k++)//当前的牧场和其余的牧场相连
        {
            int j=g[i][k];//取i到j的牧场号询问其距离
            if(dist[i]+w[i][k]<dist[j])//如果当前距离和i到k的距离小于j松弛操作
            {
                dist[j]=dist[i]+w[i][k];//松弛
                if(inq[j]!=0) continue;//询问是否在队列之中
                inq[j]=1;//不在的话再次标记
                a.push(j);//使当前的点进队好像bfs但不是bfs多次进队
            }
        }
    }
}

int main()
{
    //freopen("1.in","r",stdin);
    scanf("%d%d%d",&n,&p,&c);//n为奶牛所在的牧场号,p为4个牧场,c为5个牧场的关系
    memset(s1,0,sizeof(s1));//s1存的是奶牛的牧场位置;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&t);//
        s1[t]++;//牧场
    }
    for(int i=1;i<=c;i++)
    {
        scanf("%d%d%d",&a,&b,&d);//a与b之间的距离为d
        g[a].push_back(b);//扩边
        g[b].push_back(a);
        w[a].push_back(d);//二次扩边
        w[b].push_back(d);
    }
    int ans=inf;//附最大值
    for(int i=1;i<=p;i++)//枚举每一个牧场为起点
    {
        spfa(i);//当黄油放在第i个牧场时来一个一个判断;跑距离
        int sum=0;
        for(int j=1;j<=p;j++)
        {     
            if(!s1[j]) continue; 
            sum+=dist[j]*s1[j]; //计算奶牛到牧场的距离和
        }
        ans=min(sum,ans); //取最小值
    }
    printf("%d",ans);
    return 0;
}
View Code

注释很多很多,主要因为当时的不理解。

下面是本人今天的代码!!!

技术分享图片
#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<iomanip>
#include<algorithm>
#include<stack>
#include<ctime>
#include<vector>
#include<queue>
#include<map>
#define inf 10000000
using namespace std;
const int maxn=5000;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}
    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}
    return x*f;
}
int b[maxn],ver[maxn],lin[maxn],nex[maxn],len=0,e[maxn],minn=inf,dis[maxn],q[maxn];
bool vis[maxn];
void add(int x,int y,int z)
{
    ver[++len]=y;
    nex[len]=lin[x];
    lin[x]=len;
    e[len]=z;
}
int n,m,k,h,t;
void spfa(int x)
{
    memset(vis,0,sizeof(vis));
    memset(dis,10,sizeof(dis));
    memset(q,0,sizeof(q));
    dis[x]=0;vis[x]=1;q[1]=x;
    h=0,t=1;
    while(h<=t)
    {
        int tn=q[++h];vis[tn]=0;
        for(int i=lin[tn];i;i=nex[i])
        {
            int tmp=ver[i];
            if(dis[tn]+e[i]<dis[tmp])
            {
                dis[tmp]=dis[tn]+e[i];
                if(vis[tmp]!=1)
                {
                    q[++t]=tmp;
                    vis[tmp]=1;
                }
            }
        }
    }
}
int main()
{
    freopen("1.in","r",stdin);
    k=read();m=read();n=read();
    memset(b,0,sizeof(b));
    for(int i=1;i<=k;i++){int x;x=read();b[x]++;}
    for(int i=1;i<=n;i++)
    {
        int x,y,z;
        x=read();y=read();z=read();
        add(x,y,z);
        add(y,x,z);
    }
    for(int i=1;i<=m;i++)
    {
        int ans=0;
        spfa(i);
        for(int j=1;j<=m;j++)
        {
            if(b[j]!=0)
                ans+=dis[j]*b[j];
        }
        minn=min(ans,minn);
    }
    printf("%d\n",minn);
    return 0;
}
View Code

思路很清晰的打完了哈哈。

莫听穿林打叶声,何妨吟啸且徐行。

图论最短路——spfa

原文:https://www.cnblogs.com/chdy/p/9700429.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!