题解 P4779 【【模板】单源最短路径（标准版）】

ACAね · 2018-10-14 14:11:35 · 题解

spfa的复活之路

警告，如果你没有学会用dijkstra堆优化不建议看此篇题解

一篇诡异的非正解

因为本人很弱，所以有一些自以为是的地方，希望大家指出，但是不要乱喷...,我会改的

在三页的提交后终于用spfa切掉了这道题。。。

首先我先尝试使用了玄学(LLL,SLF?)优化，均只有68~48分，无意中发现

这个

发现数据都特意卡掉了

那就只能自食其力了

我们发现所有卡掉spfa的数据，就是诱导算法进入一个持续更新的地方

于是我尝试新加入的点入队头（dfs版）.

同时如果dis[head]>dis[tail],则交换head与tail

似乎多过了一个诶

之后我发现第一个数据非常毒瘤，死活卡不过去，因为数据太大，下不下来

但是我们可以下载输出啊!

经过一番观(xia)察(gao)

之所以卡掉前面的交换的程序，是因为这个头dis>尾dis的很多。

于是我以0.01%的概率排序整个队列，我们惊喜的发现，点1过了!

但是点3T飞

后来发现这个时间复杂度是错误的，被dijkstra爆踩

于是我们以1\div(tail-head+1)的概率排序队列，这个的期望复杂度是log的

因为sort的速度快于堆排（误

所以好像速度比dijkstra 的配对堆优化要快80ms

玄学spfa

pairing_heap_dijkstra

运用了fread和不开long long后似乎可以抢rank?

210ms左右

dijkstra

// luogu-judger-enable-o2
/*
@Date    : 2018-10-13 17:42:26
@Author  : Adscn ([email protected])
@Link    : https://www.cnblogs.com/LLCSBlog
*/
#define FASTER
#ifdef FASTER
#pragma GCC diagnostic error "-std=c++11"
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#endif
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
IL void pi(int k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
IL unsigned int LOG2(unsigned int x)
{
    unsigned int ret;
    __asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x));
    return ret;
}
typedef long long ll;
class graph{
private:
    struct edge{
        int v;
        edge *next;
        int w;
    }e[200007],*head[200007];
    int cnt;
public:
    graph(){cnt=0;}
    void add(int u,int v,int w=0)
    {
        e[cnt]=((edge){v,head[u],w});
        head[u]=&e[cnt++];
    }
    edge* begin(int u){return head[u];}
    edge* end(){return NULL;}
    class iterator{
    public:
        friend class graph;
        iterator(edge* p=NULL):__ptr(p){}
        iterator (const iterator &p):__ptr(p.__ptr){}
        iterator& operator ++()
        {
            __ptr=__ptr->next;
            return *this;
        }
        iterator operator ++(int)
        {
            iterator __tmp=(*this);
            ++(*this);
            return __tmp;
        }
        edge* operator ->(){return __ptr;}
        edge& operator * (){return *__ptr;}
        bool operator ==(const iterator &p){return __ptr==p.__ptr;}
        bool operator != (const iterator &p){return __ptr!=p.__ptr;}
    private:
        edge *__ptr;
    };
}g;
const int MAXN=100000+7;
typedef pair<ll,int> pii;
__gnu_pbds::priority_queue<pii,greater<pii> >q;
int n,m,s;
ll dis[MAXN];
bool vis[MAXN];
void dijkstra()
{
    memset(dis,0x7f7f7f,sizeof dis);
    q.push(make_pair(0,s));
    dis[s]=0;
    while(!q.empty())
    {
        int now=q.top().second;q.pop();
        if(vis[now])continue;
        vis[now]=1;
        for(graph::iterator i=g.begin(now);i!=g.end();++i)
        {
            int v=i->v;
            if(dis[v]>dis[now]+i->w)dis[v]=dis[now]+i->w,q.push(make_pair(dis[v],v));
        }
    }
}
int main(void)
{
    n=gi,m=gi,s=gi;
    for(int i=1;i<=m;i++)
    {
        int u=gi,v=gi,w=gi;
        g.add(u,v,w);
    }
    dijkstra();
    for(int i=1;i<=n;i++)pi(dis[i],' ');    
    return 0;
}

伪dfs版spfa

#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
IL void pi(int k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
IL unsigned int LOG2(unsigned int x)
{
    unsigned int ret;
    __asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x));
    return ret;
}
typedef long long ll;
class graph{
private:
    struct edge{
        int v;
        edge *next;
        int w;
    }e[200007],*head[200007];
    int cnt;
public:
    graph(){cnt=0;}
    void add(int u,int v,int w=0)
    {
        e[cnt]=((edge){v,head[u],w});
        head[u]=&e[cnt++];
    }
    edge* begin(int u){return head[u];}
    edge* end(){return NULL;}
    class iterator{
    public:
        friend class graph;
        iterator(edge* p=NULL):__ptr(p){}
        iterator (const iterator &p):__ptr(p.__ptr){}
        iterator& operator ++()
        {
            __ptr=__ptr->next;
            return *this;
        }
        iterator operator ++(int)
        {
            iterator __tmp=(*this);
            ++(*this);
            return __tmp;
        }
        edge* operator ->(){return __ptr;}
        edge& operator * (){return *__ptr;}
        bool operator ==(const iterator &p){return __ptr==p.__ptr;}
        bool operator != (const iterator &p){return __ptr!=p.__ptr;}
    private:
        edge *__ptr;
    };
}g;
const int MAXN=100000+7;
int q[20000000];
int n,m,s;
ll dis[MAXN];
bool vis[MAXN];
void dijkspfa()
{
    memset(dis,0x7f7f7f,sizeof dis);
    int l=0,r=0;
    q[l]=s;
    dis[s]=0;
    while(l<=r)
    {
        if(dis[q[l]]>dis[q[r]])swap(q[l],q[r]);
        int now=q[l++];
        vis[now]=0;
        for(graph::iterator i=g.begin(now);i!=g.end();++i)
        {
            int v=i->v;
            if(dis[v]>dis[now]+i->w)
            {
                dis[v]=dis[now]+i->w;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(l>1&&rand()%10)q[--l]=v;
                    else q[++r]=v;
                }
            }
        }
    }
}
int main(void)
{
       srand(time(0));
    n=gi,m=gi,s=gi;
    for(int i=1;i<=m;i++)
    {
        int u=gi,v=gi,w=gi;
        g.add(u,v,w);
    }
    dijkspfa();
    for(int i=1;i<=n;i++)pi(dis[i],' ');
       return 0;
}

AC spfa

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<bits/stdc++.h>
#include<bits/extc++.h>
using namespace std;
#define IL inline
#define RG register
#define gi getint()
#define gc getchar()
#define File(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout)
IL int getint()
{
    RG int xi=0;
    RG char ch=gc;
    bool f=0;
    while(ch<'0'|ch>'9')ch=='-'?f=1:f,ch=gc;
    while(ch>='0'&ch<='9')xi=(xi<<1)+(xi<<3)+ch-48,ch=gc;
    return f?-xi:xi;
}
IL void pi(int k,char ch=0)
{
    if(k<0)k=-k,putchar('-');
    if(k>=10)pi(k/10,0);
    putchar(k%10+'0');
    if(ch)putchar(ch);
}
IL unsigned int LOG2(unsigned int x)
{
    unsigned int ret;
    __asm__ __volatile__ ("bsrl %1, %%eax":"=a"(ret):"m"(x));
    return ret;
}
typedef long long ll;
class graph{
private:
    struct edge{
        int v;
        edge *next;
        int w;
    }e[200007],*head[200007];
    int cnt;
public:
    graph(){cnt=0;}
    void add(int u,int v,int w=0)
    {
        e[cnt]=((edge){v,head[u],w});
        head[u]=&e[cnt++];
    }
    edge* begin(int u){return head[u];}
    edge* end(){return NULL;}
    class iterator{
    public:
        friend class graph;
        iterator(edge* p=NULL):__ptr(p){}
        iterator (const iterator &p):__ptr(p.__ptr){}
        iterator& operator ++()
        {
            __ptr=__ptr->next;
            return *this;
        }
        iterator operator ++(int)
        {
            iterator __tmp=(*this);
            ++(*this);
            return __tmp;
        }
        edge* operator ->(){return __ptr;}
        edge& operator * (){return *__ptr;}
        bool operator ==(const iterator &p){return __ptr==p.__ptr;}
        bool operator != (const iterator &p){return __ptr!=p.__ptr;}
    private:
        edge *__ptr;
    };
}g;
const int MAXN=100000+7;
int q[30000000];
int n,m,s;
ll dis[MAXN];
bool vis[MAXN];
bool cmp(int l,int r){return dis[l]<dis[r];}
void spfa()
{
    memset(dis,0x7f7f7f,sizeof dis);
    RG int l=0,r=0;
    q[l]=s;
    dis[s]=0;
    while(l<=r)
    {
        if(rand()%((r-l+1>>3)+1)==0)sort(q+l,q+r+1,cmp);
        int now=q[l++];
        vis[now]=0;
        for(RG graph::iterator i=g.begin(now);i!=g.end();++i)
        {
            int v=i->v;
            if(dis[v]>dis[now]+i->w)
            {
                dis[v]=dis[now]+i->w;
                if(!vis[v])
                {
                    vis[v]=1;
                    if(l>1)q[--l]=v;
                    else q[++r]=v;
                }
            }
        }
    }
}
int main(void)
{
    srand(19260817);
    n=gi,m=gi,s=gi;
    for(int i=1;i<=m;i++)
    {
        int u=gi,v=gi,w=gi;
        g.add(u,v,w);
    }
    spfa();
    for(int i=1;i<=n;i++)pi(dis[i],' ');
    return 0;
}