BZOJ5109 CodePlus 2017大吉大利，晚上吃鸡！（最短路+拓扑排序+bitset）

　　首先跑正反两遍dij求由起点/终点到某点的最短路条数，这样条件一就转化为f(S,A)*f(T,A)+f(S,B)*f(T,B)=f(S,T)。同时建出最短路DAG，这样图中任何一条S到T的路径都是最短路径，对于条件二就只需要判断A是否能走到B。注意到空间开的非常大。那么对于条件二的可达性显然是可以bitset优化的。对于条件一可以map套bitset。两者and再count一下就可以了。bzoj的空间限制开小了于是这种做法就直接MLE了。

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstdlib>

#include<cstring>

#include<algorithm>

#include<queue>

#include<map>

#include<bitset>

using namespace std;

#define ll long long

#define N 50010

#define P 1000000007

char getc(){char c=getchar();while (c==||c==||c==) c=getchar();return c;}

int gcd(int n,int m){return m==?n:gcd(m,n%m);}

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

int n,m,S,T,t,p[N],f[][N],g[N];

ll d[][N];

bool flag[N];

struct data{int to,nxt,len;

}edge[N<<];

struct data2

{

    int x;ll d;

    bool operator <(const data2&a) const

    {

        return d>a.d;

    }

};

priority_queue<data2> q;

bitset<N> to[N],from[N];

map<int,bitset<N> > cnt;

void addedge(int x,int y,int z){t++;edge[t].to=y,edge[t].nxt=p[x],edge[t].len=z,p[x]=t;}

void inc(int &x,int y){x+=y;if (x>=P) x-=P;}

void dijkstra(int S,int op)

{

    memset(d[op],,sizeof(d[op]));d[op][S]=;f[op][S]=;

    memset(flag,,sizeof(flag));

    while (!q.empty()) q.pop();

    q.push((data2){S,});

    for (;;)

    {

        while (!q.empty()&&flag[q.top().x]) q.pop();

        if (q.empty()) break;

        data2 x=q.top();q.pop();

        flag[x.x]=;

        for (int i=p[x.x];i;i=edge[i].nxt)

        {

            if (x.d+edge[i].len<d[op][edge[i].to])

            {

                d[op][edge[i].to]=x.d+edge[i].len;

                q.push((data2){edge[i].to,d[op][edge[i].to]});

                f[op][edge[i].to]=;

            }

            if (x.d+edge[i].len==d[op][edge[i].to])

            inc(f[op][edge[i].to],f[op][x.x]);

        }

    }

}

namespace shortestpathDAG

{

    int p[N]={},q[N]={},degree[N]={},t=;

    struct data{int to,nxt;}edge[N];

    void addedge(int x,int y){t++;edge[t].to=y,edge[t].nxt=p[x],p[x]=t;}

    void topsort()

    {

        for (int i=;i<=t;i++) degree[edge[i].to]++;

        int head=,tail=;for (int i=;i<=n;i++) if (!degree[i]) q[++tail]=i;

        while (tail<n)

        {

            int x=q[++head];

            for (int i=p[x];i;i=edge[i].nxt)

            {

                degree[edge[i].to]--;

                if (!degree[edge[i].to]) q[++tail]=edge[i].to;

            }

        }

    }

    void work()

    {

        ll ans=;

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

        {

            int x=q[i];from[x][x]=;

            for (int j=p[x];j;j=edge[j].nxt)

            from[edge[j].to]|=from[x];

        }

        for (int i=n;i>=;i--)

        {

            int x=q[i];to[x][x]=;

            for (int j=p[x];j;j=edge[j].nxt)

            to[x]|=to[edge[j].to];

            ans+=((~(to[x]|from[x]))&cnt[(g[T]-g[x]+P)%P]).count();

        }

        cout<<(ans>>);

    }

}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("bzoj5109.in","r",stdin);

    freopen("bzoj5109.out","w",stdout);

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    n=read(),m=read(),S=read(),T=read();

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

    {

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

        addedge(x,y,z),addedge(y,x,z);

    }

    dijkstra(S,),dijkstra(T,);

    if (f[][T]==) {cout<<(1ll*n*(n-)>>);return ;}

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

    {

        if (d[][i]+d[][i]==d[][T]) g[i]=1ll*f[][i]*f[][i]%P;

        cnt[g[i]][i]=;

    }

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

    {

        if (d[][edge[i+].to]+d[][edge[i].to]+edge[i].len==d[][T]) shortestpathDAG::addedge(edge[i+].to,edge[i].to);

        if (d[][edge[i].to]+d[][edge[i+].to]+edge[i].len==d[][T]) shortestpathDAG::addedge(edge[i].to,edge[i+].to);

    }

    shortestpathDAG::topsort();

    shortestpathDAG::work();

    return ;

}

BZOJ5109 CodePlus 2017大吉大利，晚上吃鸡！（最短路+拓扑排序+bitset）的相关教程结束。