[BZOJ5109/CodePlus2017]大吉大利，晚上吃鸡！

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

输出一行表示答案

Sample Input

7 7 1 7

1 2 2

2 4 2

4 6 2

6 7 2

1 3 2

3 5 4

5 7 2

Sample Output

首先预祝你们落地成盒（逃

话说大家喜欢用些什么枪啊，步枪还是狙击枪（ヽ(￣︿￣　)—C<(/°Д°)/，又不好好讲题了，拖走

咳，我们还是回到正题，首先我们简化一下题面：若存在点对\((x,y)\)，满足所有S到T的最短路，存在任意一条经过且只经过一个点，且所有最短路不会同时经过两个点，那么这个点对就是合法的，求合法点对的个数

首先我们求出所有S到T的最短路，将其作为一张新图，并统计新图内的点数，首先利用乘法原理，一个点在最短路上，一个点不在，求出一部分答案。

然后考虑新图内的答案，我们在选定一个点之后，该点向T方向走能到达的所有点都是不可选的，同理，所有从S方向能走到它的点也是不可选的。如何记录这些点？Hash或bitset。然后由于会算重，我们除2即可

注意，如果S->T不连通，我们需要输出\(\binom{n}{2}\)

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 1e18

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)	print(x/10);

	putchar(x%10+'0');

}

const int N=5e4;

int pre[(N<<1)+10],now[N+10],child[(N<<1)+10],val[(N<<1)+10];

int tot;

ll Ans,Low_Dis;

struct S1{

	ll dis[N+10];

	S1(){memset(dis,63,sizeof(dis));}

}Frw,Bck;

int h[N+10],f[N+10];

bool vis[N+10],In[N+10];

void join(int x,int y,int z){pre[++tot]=now[x],now[x]=tot,child[tot]=y,val[tot]=z;}

void insert(int x,int y,int z){join(x,y,z),join(y,x,z);}

void SPFA(int x,ll *dis){

	int head=0,tail=1;

	h[1]=x,dis[x]=0,vis[x]=1;

	while (head!=tail){

		if (++head>N)	head=1;

		int Now=h[head];

		for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){

			if (dis[son]>dis[Now]+val[p]){

				dis[son]=dis[Now]+val[p];

				if (!vis[son]){

					if (++tail>N)	tail=1;

					vis[h[tail]=son]=1;

				}

			}

		}

		vis[Now]=0;

	}

}

bitset<N>bit[N+10],tmp(1);

void dfs_S(int x,int fa,int T){

	bit[x]|=tmp<<(x-1);

	if (x==T)	return;

	for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){

		if (son==fa||Frw.dis[x]+val[p]+Bck.dis[son]!=Low_Dis)	continue;

		dfs_S(son,x,T);

		bit[x]|=bit[son];

	}

}

void dfs_T(int x,int fa,int T){

	bit[x]|=tmp<<(x-1);

	if (x==T)	return;

	for (int p=now[x],son=child[p];p;p=pre[p],son=child[p]){

		if (son==fa||Bck.dis[x]+val[p]+Frw.dis[son]!=Low_Dis)	continue;

		dfs_T(son,x,T);

		bit[x]|=bit[son];

	}

}

int main(){

	int n=read(),m=read(),S=read(),T=read(),All=0;

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

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

		insert(x,y,z);

	}

	SPFA(S,Frw.dis);

	SPFA(T,Bck.dis);

	Low_Dis=Frw.dis[T];

	for (int i=1;i<=n;i++)	if (Frw.dis[i]+Bck.dis[i]==Low_Dis)	In[i]=1,All++;

	if (Low_Dis>inf){

		printf("%lld\n",1ll*n*(n-1)/2);

		return 0;

	}

	dfs_S(S,0,T);

	for (int i=1;i<=n;i++)	if (In[i])	f[i]+=bit[i].count(),bit[i].reset();

	dfs_T(T,0,S);

	for (int i=1;i<=n;i++)	if (In[i])	f[i]+=bit[i].count()-1;

	Ans=1ll*All*(n-All);

	ll res=0;

	for (int i=1;i<=n;i++)	if (In[i])	res+=All-f[i];

	printf("%lld\n",Ans+(res>>1));

	return 0;

}