Description
最近《绝地求生：大逃杀》风靡全球，皮皮和毛毛也迷上了这款游戏，他们经常组队玩这款游戏。在游戏中，皮皮
和毛毛最喜欢做的事情就是堵桥，每每有一个好时机都能收到不少的快递。当然，有些时候并不能堵桥，皮皮和毛
毛会选择在其他的必经之路上蹲点。K博士作为一个老年人，外加有心脏病，自然是不能玩这款游戏的，但是这并
不能妨碍他对这款游戏进行一些理论分析，比如最近他就对皮皮和毛毛的战士很感兴趣。【题目描述】游戏的地图
可以抽象为一张n个点m条无向边的图，节点编号为1到n，每条边具有一个正整数的长度。假定大魔王都会从S点出
发到达T点（S和T已知），并且只会走最短路，皮皮和毛毛会在A点和B点埋伏大魔王。
为了保证一定能埋伏到大魔王，同时又想留大魔王一条生路，皮皮和毛毛约定A点和B点必须满足：
1.大魔王所有可能路径中，必定会经过A点和B点中的任意一点
2.大魔王所有可能路径中，不存在一条路径同时经过A点和B点
K博士想知道，满足上面两个条件的A,B点对有多少个，交换A,B的顺序算相同的方案
Input
第一行输入四个整数n,m,S,T(1≤n≤5×10^4,1≤m≤5×10^4,1≤S,T≤n)，含义见题目描述。
接下来输入m行，每行输入三个整数u,v,w(1≤u,v≤n,1≤w≤10^9)表示存在一条长度为w的边链接u和v。
1≤n≤5×10^4,1≤m≤5×10^4,1≤w≤10^9
Output
输出一行表示答案
求出S-T最短路图，以及传递闭包
任选一个以T为根的树形图，对每条非树边u->v，选一个随机数x，将v的父亲和u分别到根的路径异或上x
若S和T不联通，任选两个点
否则，可以选两个点，使得其中一个点不在最短路图上，另一个点为最短路图上点权为0的点，或者选最短路图上两个互不能到达且权值相同且非零的点
#include<bits/stdc++.h>
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned int u32;
const int N=5e4+;
char ib[N*],*ip=ib;
int _(){int x;scanf("%d",&x);return x;}
int n,m,S,T,e0[N],ep=;
i64 l[N],ans=;
struct edge{
int to,v,nx;
}e[N*];
struct node{
int w;
i64 l;
bool operator<(const node&w)const{return l>w.l;}
};
std::priority_queue<node>q;
bool ed[N];
struct pos{
int w;
u64 v,l;
bool operator<(const pos&x)const{return v!=x.v?v<x.v:l>x.l;}
}ps[N];
u64 f[N];
int fa[N],pp=,cp=;
u32 su[N][N/+];
void f1(int w){
ed[w]=;
for(int i=e0[w];i;i=e[i].nx){
int u=e[i].to;
if(l[u]+e[i].v==l[w]){
if(!ed[u])fa[u]=w,f1(u);
else{
u64 z=rand();
z=z<<^rand();
f[w]^=z;
f[fa[u]]^=z;
}
}
}
}
int _get(u32*a,int x){return a[x>>]>>x&;}
void _set(u32*a,int x){a[x>>]|=<<x;}
void _or(u32*a,u32*b){
int p=n/+;
for(int i=;i<p;i+=){
a[i]|=b[i];
a[i+]|=b[i+];
a[i+]|=b[i+];
a[i+]|=b[i+];
}
}
void f2(int w){
_set(su[w],w);
ed[w]=;
for(int i=e0[w];i;i=e[i].nx){
int u=e[i].to;
if(l[u]+e[i].v==l[w]){
if(ed[u])f2(u),f[w]^=f[u];
_or(su[w],su[u]);
}
}
if(f[w])ps[pp++]=(pos){w,f[w],l[w]};
else ++cp;
}
void cal(){
f1(T);
f2(T);
std::sort(ps,ps+pp);
for(int i=,j=;i<pp;i=j){
int t=;
for(++j;j<pp&&ps[i].v==ps[j].v;++j)t+=_get(su[ps[i].w],ps[j].w);
ans+=i64(j-i-t)*t;
}
ans+=cp*i64(n-cp-pp);
printf("%lld\n",ans);
}
int main(){
n=_();m=_();S=_();T=_();
srand(n^m^S^T^);
for(int i=;i<m;++i){
int a=_(),b=_(),c=_();
e[ep]=(edge){b,c,e0[a]};e0[a]=ep++;
e[ep]=(edge){a,c,e0[b]};e0[b]=ep++;
}
for(int i=;i<=n;++i)l[i]=1ll<<;
q.push((node){S,l[S]=});
while(q.size()){
node w=q.top();q.pop();
if(w.l!=l[w.w])continue;
if(w.w==T)return cal(),;
for(int i=e0[w.w];i;i=e[i].nx){
int u=e[i].to;
if(l[u]>w.l+e[i].v)q.push((node){u,l[u]=w.l+e[i].v});
}
}
printf("%lld\n",n*i64(n-)/);
return ;
}