BZOJ3040 最短路 测评报告

2014.12.09 23:21 Tue| 15 visits oi_2015| 2015_刷题日常| Text

Solution

这道题的题意清楚明白:

N个点,M条边的有向图,求点1到点N的最短路(保证存在)。

1<=N<=1000000,1<=M<=10000000

题解也清楚明白:

请采用高效的堆来优化Dijkstra算法。

于是我们来尝试各种“高效”的堆吧~

pb_ds Pairing-Heap

看了网上题解,应该说绝大多数小盆友们都用的这个pb_ds库里的好东西~

这样跑出来的结果是7204ms,可以说相当可观了。可惜NOI系列比赛中是否允许使用有待商榷。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <ext/pb_ds/priority_queue.hpp>
using namespace std;
using namespace __gnu_pbds;
#define N 1000005
#define M 10000005
long long d[N];
int n,m,t,rxa,rxc,rya,ryc,rp;
int head[N],next[M],to[M],val[M],cnt;
__gnu_pbds::priority_queue< pair<long long,int>,greater< pair<long long,int> >,pairing_heap_tag > q;
__gnu_pbds::priority_queue< pair<long long,int>,greater< pair<long long,int> >,pairing_heap_tag >::point_iterator id[1000005];
void add(int x,int y,int z)
{
    val[++cnt]=z;
    to[cnt]=y;
    next[cnt]=head[x];
    head[x]=cnt;
}
void spfa(int s)
{
    memset(d,0x3f,sizeof d);
    id[1]=q.push(make_pair(0,s));d[s]=0;
    while(!q.empty())
    {
        int x=q.top().second,y;q.pop();
        for(int i=head[x];i;i=next[i])
        {
            if(d[y=to[i]]>d[x]+val[i])
            {
                d[y]=d[x]+val[i];
                if(id[y]!=0)
                    q.modify(id[y],make_pair(d[y],y));
                else id[y]=q.push(make_pair(d[y],y));
            }
        }
    }
}
inline void read(int &a)
{
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    a=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        a=(a<<3)+(a<<1)+ch-'0';
}
int main()
{
    cin>>n>>m;
    cin>>t>>rxa>>rxc>>rya>>ryc>>rp;
    int x=0,y=0,z=0,a,b;
    for(int i=1;i<=t;i++)
    {
        x=(x*rxa+rxc)%rp;
        y=(y*rya+ryc)%rp;
        a=min(x%n+1,y%n+1);
        b=max(y%n+1,y%n+1);
        add(a,b,100000000-100*a);
    }
    for(int i=t+1;i<=m;i++)
    {
        read(x),read(y),read(z);
        add(x,y,z);
    }
    spfa(1);
    cout<<d[n]<<endl;
}

传说中的Fibonacci堆

蒟蒻不会Fibonacci堆233,好在我们有LYD神犇(这可是出题人啊)的代码。

42440ms。和STL里的配对堆根本没法比啊!!!这个事实好像已经足以让人破灭对Fibonacci堆的幻想了?但是没关系,至少可以AC。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
const int u=1000005,w=10000005;
struct Fibonacci_Heap{
    int du,fa,child,next,last,mark;
    #define du(x) heap[x].du
    #define fa(x) heap[x].fa
    #define ch(x) heap[x].child
    #define r(x) heap[x].next
    #define l(x) heap[x].last
    #define mark(x) heap[x].mark
}heap[u];
int head[u],v[u],ver[w],edge[w],next[w];
vector<int> a[25];
long long d[u],rxa,rxc,rya,ryc,rza,rzc;
int p,n,m,t,tot,x,y,z,rp;

inline void add(int x,int y,int z)
{
    ver[++tot]=y,edge[tot]=z,next[tot]=head[x],head[x]=tot;
}

inline void Link(int x,int y)
{
    if(!x||!y) return;
    l(r(x))=l(y),r(l(y))=r(x);
    r(x)=y,l(y)=x;
}

inline void Cut(int x)
{
    if(ch(fa(x))==x) ch(fa(x))=r(x)==x?0:r(x);
    du(fa(x))--;
    r(l(x))=r(x),l(r(x))=l(x);
    l(x)=r(x)=x;
    fa(x)=mark(x)=0;
}

void Insert(int x)
{
    l(x)=r(x)=x,v[x]=1;
    Link(x,p);
    if(d[x]<d[p]) p=x;
}

void Decrease(int x)
{
    if(!fa(x))
    {
        if(d[x]<d[p]) p=x;
        return;
    }
    if(d[x]>=d[fa(x)]) return;
    do{
        int y=fa(x);
        Cut(x),Link(p,x);
        if(d[x]<d[p]) p=x;
        x=y;
    }while(mark(x));
    if(fa(x)) mark(x)=1;
}

void Extract()
{
    int i,j,x,y;
    for(i=r(p);i!=p;i=r(i)) a[du(i)].push_back(i);
    if(i=ch(p)) a[du(i)].push_back(i);
    for(i=r(i);i!=ch(p);i=r(i)) a[du(i)].push_back(i);
    for(p=i=0;i<25;i++)
    {
        for(j=a[i].size()-1;j>=0;j--)
            if(j)
            {
                x=a[i][j],y=a[i][--j];
                if(d[y]<d[x]) swap(x,y);
                l(y)=r(y)=y;
                Link(ch(x),y);
                ch(x)=y,fa(y)=x,du(x)++;
                a[i+1].push_back(x);
            }
            else{
                x=a[i][j],l(x)=r(x)=x,fa(x)=mark(x)=0;
                Link(p,x);
                if(d[x]<d[p]) p=x;
            }
        a[i].clear();
    }
}

void Fibonacci_Heap_Dijkstra()
{
    memset(d,0x7f,sizeof(d));
    d[1]=0;
    Insert(1);
    for(int t=1;t<=n;t++)
    {
        if(!p) return;
        int x=p;
        Extract();
        for(int i=head[x],y;i;i=next[i])
            if(d[y=ver[i]]>d[x]+edge[i])
            {
                d[y]=d[x]+edge[i];
                if(v[y]) Decrease(y); else Insert(y);
            }
    }
}

int main()
{
    cin>>n>>m;
    cin>>t>>rxa>>rxc>>rya>>ryc>>rp;
    for(int i=1;i<=m-t;i++)
    {
        scanf("%d%d%d",&x,&y,&z);
        add(x,y,z);
    }
    x=y=z=0;
    for(int i=1;i<=t;i++)
    {
        x=(x*rxa+rxc)%rp;
        y=(y*rya+ryc)%rp;
        int A=x%n+1,B=y%n+1;
        if(A>B) swap(A,B);
        z=100000000-100*A;
        add(A,B,z);
    }
    Fibonacci_Heap_Dijkstra();
    cout<<d[n]<<endl;
    return 0;
}

普通映射堆

PoPoQQQ坚持这道题如果用STL水就丧失了意义。因此,他立志自己写出配对堆……咦?先写出一个暴力交上去试试,怎么A掉了?……

观察随机数的生成方式,得到另一种解决方案

每一条边由于生成方式决定绝大多数边是在绕圈子233。实际上,前T条边一条也不用加……

我们这么叼,出题人知道么?

咦?LYD的代码中好像安静地躺着四个不起眼的字符……

这样,此题无论怎样都可以AC了……

删前T条边,pb_ds Pairing Heap

时间瞬间降到了2824ms,已经非常优越了。

删前T条边,priority_queue

再来试一下PQ。常规堆优化SPFA写法。

纳尼?时间2812ms!这不科学啊!

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define M 1000005
long long d[N];
int n,m,t,rxa,rxc,rya,ryc,rp;
int head[N],next[M],to[M],val[M],cnt;
priority_queue<pair<int,int> > q;
void add(int x,int y,int z)
{
    val[++cnt]=z;
    to[cnt]=y;
    next[cnt]=head[x];
    head[x]=cnt;
}
void spfa(int s)
{
    memset(d,0x3f,sizeof d);
    q.push(make_pair(0,s));d[s]=0;
    while(!q.empty())
    {
        int x=q.top().second,y=-q.top().first; q.pop();
        if(y!=d[x]) continue;
        y=0;
        for(int i=head[x];i;i=next[i])
            if(d[y=to[i]]>d[x]+val[i])
                d[y]=d[x]+val[i],
                q.push(make_pair(-d[y],y));
    }
}
inline void read(int &a)
{
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    a=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        a=(a<<3)+(a<<1)+ch-'0';
}
int main()
{
    cin>>n>>m;
    cin>>t>>rxa>>rxc>>rya>>ryc>>rp;
    int x=0,y=0,z=0,a,b;
    for(int i=t+1;i<=m;i++)
    {
        read(x),read(y),read(z);
        add(x,y,z);
    }
    spfa(1);
    cout<<d[n]<<endl;
}

赤果果的SPFA

来试一试赤果果的SPFA好了。4412ms,还真是经济适用。

#include <bits/stdc++.h>
using namespace std;
#define N 1000005
#define M 1000005
long long d[N]; bool v[N];
int n,m,t,rxa,rxc,rya,ryc,rp;
int head[N],next[M],to[M],val[M],cnt;
queue<int> q;
void add(int x,int y,int z)
{
    val[++cnt]=z;
    to[cnt]=y;
    next[cnt]=head[x];
    head[x]=cnt;
}
void spfa(int s)
{
    memset(d,0x3f,sizeof d);
    q.push(s);d[s]=0;
    while(!q.empty())
    {
        int x=q.front(); q.pop(); v[x]=0;
        for(int i=head[x],y;i;i=next[i])
            if(d[y=to[i]]>d[x]+val[i])
            {
                d[y]=d[x]+val[i];
                if(!v[y])
                    q.push(y),v[y]=1;
            }
    }
}
inline void read(int &a)
{
    char ch;
    while((ch=getchar())<'0'||ch>'9');
    a=ch-'0';
    while((ch=getchar())>='0'&&ch<='9')
        a=(a<<3)+(a<<1)+ch-'0';
}
int main()
{
    cin>>n>>m;
    cin>>t>>rxa>>rxc>>rya>>ryc>>rp;
    int x=0,y=0,z=0,a,b;
    for(int i=t+1;i<=m;i++)
    {
        read(x),read(y),read(z);
        add(x,y,z);
    }
    spfa(1);
    cout<<d[n]<<endl;
}

还有PoPoQQQ的配对堆

最终删去前T条边一共4140B的代码量,2028ms。我想说我以后还是乖乖写我的PQ好了。。。

删前T条边,Fibonacci堆

到这里,只能说LYDrainbowcat的Fibonacci写得太……了。。

删去T条边之后加读入优化得到的结果是3880ms,仅仅强于裸SPFA。为出题人LYD默哀。。