题目分享F 二代目

题意：T个点R种双向边，P种单向边，求点S到每个点的最短距离

分析：（这再看不出来是spfa就该**了）

首先，这题能否用spfa就看他是否有负环呗，显然，双向边的权值非负，单向边还有个啥政策，总之显然是没有负环了

那么直接跑裸的spfa

没想到竟然t了

难不成spfa还有优化？

我带着怀疑的心情上了百度，艹还真有

　　SLF优化：

　　SLF优化，即 Small Label First 策略，使用双端队列进行优化。

　　一般可以优化15%~20%，在竞赛中比较常用。

　　设从 u 扩展出了 v ，队列中队首元素为 k ，若 dis[ v ] < dis[ k ] ，则将 v 插入队首，否则插入队尾。

　　注：队列为空时直接插入队尾。

妙啊，我加上这个优化直接就过了，代码也很好写

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

const int maxm=2e5+;

const int maxn=3e4+;

const int inf=0x3f3f3f3f;

struct Node

{

    int to,next,val;

}e[maxm];

int head[maxn];

int dis[maxn];

bool vis[maxn];

int cnt;

void add(int x,int y,int z)

{

    e[++cnt].to=y;

    e[cnt].val=z;

    e[cnt].next=head[x];

    head[x]=cnt;

}

int read()

{

    char ch=getchar();int ans=,p=;

    while(ch>''||ch<'')

    {

        if(ch=='-') p=-;

        ch=getchar();

    }

    while(ch<=''&&ch>='')

    {

        ans=(ans<<)+(ans<<)+ch-'';

        ch=getchar();

    }

    return ans*p;

}

void spfa(int x)

{

    memset(dis,0x3f,sizeof(dis));

    deque<int> q;q.push_back(x),dis[x]=;

    while(!q.empty())

    {

        int now=q.front();q.pop_front();

        vis[now]=;

        for(int i=head[now];i;i=e[i].next)

        {

            int v=e[i].to;

            if(dis[v]>dis[now]+e[i].val)

            {

                dis[v]=dis[now]+e[i].val;

                if(!vis[v])

                {

                    vis[v]=;

                    if(!q.empty()&&dis[v]<dis[q.front()]) q.push_front(v);

                    else q.push_back(v);

                }

            }

        }

    }

}

int main()

{

    int t,r,p,s,x,y,z;

    t=read(),r=read(),p=read(),s=read();

    while(r--)

    {

        x=read(),y=read(),z=read();

        add(x,y,z),add(y,x,z);

    }

    while(p--)

    {

        x=read(),y=read(),z=read();

        add(x,y,z);

    }

    spfa(s);

    for(int i=;i<=t;i++)

    {

        if(dis[i]==inf) printf("NO PATH\n");

        else printf("%d\n",dis[i]);

    }

    return ;

}

然后我接着往下看，还有一个优化

　　LLL优化：

　　LLL优化，即 Large Label Last 策略，使用双端队列进行优化。

　　一般用SLF+LLL可以优化50%左右，但是在竞赛中并不常用LLL优化。

　　设队首元素为 k ，每次松弛时进行判断，队列中所有 dis 值的平均值为 x 。

　　若 dist[ k ] > x ，则将 k 插入到队尾，查找下一元素，直到找到某一个 k 使得 dis[ k ] <= x ，则将 k 出队进行松弛操作。

我也给他写出来了

#include<cstdio>

#include<queue>

#include<algorithm>

#include<cstring>

using namespace std;

#define ll long long

const int maxm=2e5+;

const int maxn=3e4+;

const int inf=0x3f3f3f3f;

struct Node

{

    int to,next,val;

}e[maxm];

int head[maxn];

int dis[maxn];

bool vis[maxn];

int cnt;

void add(int x,int y,int z)

{

    e[++cnt].to=y;

    e[cnt].val=z;

    e[cnt].next=head[x];

    head[x]=cnt;

}

int read()

{

    char ch=getchar();int ans=,p=;

    while(ch>''||ch<'')

    {

        if(ch=='-') p=-;

        ch=getchar();

    }

    while(ch<=''&&ch>='')

    {

        ans=(ans<<)+(ans<<)+ch-'';

        ch=getchar();

    }

    return ans*p;

}

void spfa(int x)

{

    int num=;ll sum=;

    memset(dis,0x3f,sizeof(dis));

    deque<int> q;q.push_back(x),dis[x]=;

    while(!q.empty())

    {

        int now=q.front();q.pop_front();

        num--,sum-=dis[now];

        while(num&&dis[now]>sum/num)

        {

            q.push_back(now);

            now=q.front();

            q.pop_front();

        }

        vis[now]=;

        for(int i=head[now];i;i=e[i].next)

        {

            int v=e[i].to;

            if(dis[v]>dis[now]+e[i].val)

            {

                dis[v]=dis[now]+e[i].val;

                if(!vis[v])

                {

                    vis[v]=;

                    if(!q.empty()&&dis[v]<dis[q.front()]) q.push_front(v);

                    else q.push_back(v);

                    num++,sum+=dis[v];

                }

            }

        }

    }

}

int main()

{

    int t,r,p,s,x,y,z;

    t=read(),r=read(),p=read(),s=read();

    while(r--)

    {

        x=read(),y=read(),z=read();

        add(x,y,z),add(y,x,z);

    }

    while(p--)

    {

        x=read(),y=read(),z=read();

        add(x,y,z);

    }

    spfa(s);

    for(int i=;i<=t;i++)

    {

        if(dis[i]==inf) printf("NO PATH\n");

        else printf("%d\n",dis[i]);

    }

    return ;

}

令我没想到的是，这俩加起来竟然又t了

也可能是我写的不对，也有可能这个优化被卡了

总之以后我写spfa一定会带上SLF优化的，

这个题大概老姚是想让我们了解一下spfa的优化吧？

代码：上面给过了

巴特西

题目分享F 二代目

最新文章

热门文章