luogu4061 大吉大利，晚上吃鸡！

链接

最短路径\(dag\)，一道好题。
题目大意：求一张图中满足下列要求的点对\((i,j)\)数量：
所有最短路径必定会经过 \(i\) 点和 \(j\) 点中的任意一点。
不存在一条最短路同时经过 \(i\) 点和 \(j\) 点。
考虑这两个限制是啥。
首先所有最短路要么经过\(i\)点，要么经过\(j\)点，不存在两个都不经过或者都经过的。
所以经过\(i\)点的最短路方案加上经过\(j\)点的最短路方案不存在交集。
那么考虑怎么求最短路方案，先做一边\(dij\)，然后在\(tag\)上\(dp\)方案数即可，正反都做一遍。
那么有\(f_{i,0}\)表示从\(s\)到\(i\)正向最短路方案数，
经过\(i\)点的最短路方案设为\(F_{i}\)，有$${F_{i}=f_{i,0}*f_{i,1}}$$
所以满足要求的\(i,j\)可写为：$$F_i+F_j=F_t$$。
这个满足了还不够，因为这个只是\(i,j\)的必要条件，还不是充分条件。
关键在于所有的路径不能同时经过这两个点。
设\(G_{i,0}\)表示从\(s\)点到\(i\)点可能经过的点集，\(bitset\)实现，\(G_{i,1}\)同理。
转移拓扑排序实现即可。
所以我们对于每一个\(i\)，想知道\(F_{t}-F_{i}=F_{j}\)中，\(j\)的点数，减去\(i\)可以到达的点数。
维护一个\(map\)，记录\(F_{j}\)这个集合中的点。
那么对于一个\(i\)，他能产生的贡献就是集合$$S=G_{F_t-F_i}\ and\ G_{i,0}\ and \ G_{i,1}$$
的\(1\)的个数。
空间\(1GB\)就可以过

// luogu-judger-enable-o2

#include<bits/stdc++.h>

#define R register int

#define ll long long

using namespace std;

const int N=50001;

const int M=100001;

const ll inf=1e18;

const int mod=1000000009;

int n,m,s,u,v,x,t,ans,vis[N];

int cnt,nt[M],to[M],hd[N],w[M];

int du[N];

ll Dis[2][N],f[2][N],F[N];

void link(R f,R t,R d){nt[++cnt]=hd[f],to[cnt]=t,w[cnt]=x,hd[f]=cnt;}

bitset<50001>G[2][N];

map<ll,bitset<50001> >Ms;

int gi(){

    R x=0,k=1;char c=getchar();

    while((c<'0'||c>'9')&&c!='-')c=getchar();

    if(c=='-')k=-1,c=getchar();

    while(c>='0'&&c<='9')x=(x<<3)+(x<<1)+c-'0',c=getchar();

    return x*k;

}

struct ip{int id;ll val;};

int operator < (ip x,ip y){return x.val>y.val;}

priority_queue<ip>Q;

void dij(R op){

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

    for(R i=1;i<=n;++i)vis[i]=0,Dis[op][i]=inf;

    if(op)Dis[1][t]=0,Q.push((ip){t,0}),f[op][t]=1;

    else Dis[0][s]=0,Q.push((ip){s,0}),f[op][s]=1;

    while(!Q.empty()){

        ip s=Q.top();Q.pop();

        if(vis[s.id])continue;

        R i=s.id;vis[i]=1;

        for(R k=hd[i];k;k=nt[k]){

            if(Dis[op][to[k]]>Dis[op][i]+w[k]){

                Dis[op][to[k]]=Dis[op][i]+w[k];

                f[op][to[k]]=f[op][i],Q.push((ip){to[k],Dis[op][to[k]]});

            }

            else if(Dis[op][to[k]]==Dis[op][i]+w[k])

                f[op][to[k]]+=f[op][i];

        }

    }

}

queue<int>til;

void top(R op){

    for(R i=1;i<=n;++i)

        for(R k=hd[i];k;k=nt[k])

            if(Dis[op][i]+w[k]+Dis[!op][to[k]]==Dis[0][t])

                du[to[k]]++;

    for(R i=1;i<=n;++i){

        G[op][i].set(),G[op][i][0]=G[op][i][i]=0;

        if(!du[i])til.push(i);

    }

    while(!til.empty()){

        R i=til.front();til.pop();

        for(R k=hd[i];k;k=nt[k])

            if(Dis[op][i]+w[k]+Dis[!op][to[k]]==Dis[0][t]){

                du[to[k]]--,G[op][to[k]]&=G[op][i];

                if(!du[k])til.push(to[k]);

            }

    }

}

int main(){

    n=gi(),m=gi(),s=gi(),t=gi();

    for(R i=1;i<=m;++i)

        u=gi(),v=gi(),x=gi(),link(u,v,x),link(v,u,x);

    dij(0),dij(1);

    if(!f[0][t])return printf("%lld",1ll*n*(n-1)/2),0;

    for(R i=1;i<=n;++i)

        if(Dis[0][i]+Dis[1][i]==Dis[0][t])

            F[i]=f[0][i]*f[1][i];

    top(0),top(1);

    for(R i=1;i<=n;++i)Ms[F[i]].set(i);

    for(R i=1;i<=n;++i)

        ans+=(Ms[F[t]-F[i]]&G[0][i]&G[1][i]).count();

    cout<<(ans>>1);

    return 0;

}

luogu4061 大吉大利，晚上吃鸡！的相关教程结束。