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 ;
}