「CodePlus 2017 11 月赛」大吉大利，晚上吃鸡！

n<=50000，m<=50000的图，给s和t，问有多少点对$(a,b)$满足

嗯。

不会。

首先最短路DAG造出来，然后两个条件转述一下：条件一，$N_a$表示从s到t经过a的路径，$N_a+N_b=N_t$；条件二，在最短路DAG上A不能到B，B不能到A。

条件一就迪杰斯特拉的时候算一下N，注意不在最短路DAG上的点$N_i=0$；然后对每个$N_t-N_b$的值存一个bitset，用以表示值为这么多的点的状态，枚举a查多少$N_t-N_b=N_a$即可。

条件二就正反拓扑序跑一下，然后传递闭包算出来即可知道最短路图上哪些点能到a和a能到哪些点，把这些点设为不可达点，取个交集即可算出每个a能和哪些b在条件二下配对。

然后就没了。

 #include<stdio.h>

 #include<string.h>

 #include<algorithm>

 #include<stdlib.h>

 #include<bitset>

 #include<queue>

 #include<math.h>

 //#include<time.h>

 //#include<iostream>

 using namespace std;

 int n,m,s,t;

 #define maxn 50011

 #define maxm 100011

 #define LL long long

 struct Edge{int to,next,v;};

 struct qnode

 {

     int id; LL v;

     bool operator < (const qnode &b) const {return v<b.v;}

     bool operator > (const qnode &b) const {return v>b.v;}

 };

 struct Graph

 {

     Edge edge[maxm<<]; int first[maxn],le;

     Graph() {memset(first,,sizeof(first)); le=;}

     void in(int x,int y,int v) {Edge &e=edge[le]; e.to=y; e.v=v; e.next=first[x]; first[x]=le++;}

     void insert(int x,int y,int v) {in(x,y,v); in(y,x,v);}

     priority_queue<qnode,vector<qnode>,greater<qnode> > q;

     void dijkstra(int s,LL *dis,LL *f)

     {

         for (int i=;i<=n;i++) dis[i]=1e18,f[i]=;

         dis[s]=; f[s]=;

         q.push((qnode){s,});

         while (!q.empty())

         {

             const int now=q.top().id; const LL d=q.top().v; q.pop();

             if (d!=dis[now]) continue;

             for (int i=first[now];i;i=edge[i].next)

             {

                 const Edge &e=edge[i];

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

                 {

                     dis[e.to]=dis[now]+e.v;

                     f[e.to]=f[now];

                     q.push((qnode){e.to,dis[e.to]});

                 }

                 else if (dis[e.to]==dis[now]+e.v) f[e.to]+=f[now];

             }

         }

     }

 }g;

 LL dis[][maxn],f[][maxn],val[maxn];

 bitset<maxn> where[maxn],can[][maxn];

 int indo[maxn],head,tail,que[maxn];

 bool check(int x,int y,int v,int ty) {return dis[ty][x]+v+dis[ty^][y]==dis[][t];}

 void toposort(int ty)

 {

     memset(indo,,sizeof(indo));

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

         for (int j=g.first[i];j;j=g.edge[j].next)

         {

             const Edge &e=g.edge[j];

             if (check(i,e.to,e.v,ty)) indo[e.to]++;

         }

     head=tail=;

     for (int i=;i<=n;i++) if (indo[i]==) que[tail++]=i;

     while (head!=tail)

     {

         const int now=que[head++];

         for (int i=g.first[now];i;i=g.edge[i].next)

         {

             const Edge &e=g.edge[i];

             if (!check(now,e.to,e.v,ty)) continue;

             indo[e.to]--; if (indo[e.to]==) que[tail++]=e.to;

             can[ty][e.to]&=can[ty][now];

         }

     }

 }

 qnode list[maxn];

 int main()

 {

     scanf("%d%d%d%d",&n,&m,&s,&t);

     for (int i=,x,y,v;i<=m;i++)

     {

         scanf("%d%d%d",&x,&y,&v);

         g.insert(x,y,v);

     }

     g.dijkstra(s,dis[],f[]); g.dijkstra(t,dis[],f[]);

     if (dis[][t]==1e18) {printf("%lld\n",1ll*n*(n-)/); return ;}

     for (int i=;i<=n;i++) can[][i].set(),can[][i].set(),can[][i][i]=can[][i][i]=;

     toposort(); toposort();

     for (int i=;i<=n;i++) if (dis[][i]+dis[][i]!=dis[][t]) val[i]=; else val[i]=f[][i]*f[][i];

     for (int i=;i<=n;i++) list[i]=((qnode){i,val[i]});

     sort(list+,list++n);

     list[n+].v=1e18;

     for (int i=,j=;i<=n+;i++) if (list[i].v!=list[i-].v)

     {

         int now=j;

         for (;j<i;j++) where[now][list[j].id]=;

     }

     LL ans=;

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

     {

         int L=,R=n+; LL tmp=f[][t]-val[i];

         while (L<R)

         {

             int mid=(L+R)>>;

             if (list[mid].v>=tmp) R=mid;

             else L=mid+;

         }

         if (L!=n+) ans+=(where[L]&can[][i]&can[][i]).count();

     }

     printf("%lld\n",ans/);

     return ;

 }