规避（Evade）

【一句话题意】给你一个图源点s和汇点t，先求得最短路，再在最短路上，求在s和t同时出发，不相遇不重复的路径方案数。对1e9+7取模。
【分析】考虑容斥原理，不考虑相遇，则方案数为{最短路条数}²。再排除在边上相遇的情况{f[u]*g[v]}²和在点上相遇的情况{f[u]*g[u]}²。
f、g数组为从s（或t）走最短路出发到点i的方案数。
细节上处理的关键在于从整张图中抽离出最短路再进行dp。
【code】

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
const int maxn=1e5+1000;
struct Edge{
	int v,nxt;
	LL c;
}edge[maxn<<2];
int head[maxn],tot;
int n,m,s,t;
inline void read(int &x){
	x=0;int fl=1;char tmp=getchar();
	while(tmp<'0'||tmp>'9'){if(fl=='-')fl=-fl;tmp=getchar();}
	while(tmp>='0'&&tmp<='9') x=(x<<1)+(x<<3)+tmp-'0',tmp=getchar();
}
inline void add_edge(int x,int y,int c){
	edge[tot].v=y;
	edge[tot].c=c;
	edge[tot].nxt=head[x];
	head[x]=tot++;
}
int p[maxn];
LL dist[maxn],f[maxn],g[maxn],ans;
bool inq[maxn];
inline void spfa(){
	memset(dist,0x3f,sizeof(dist));
	queue<int> q;
	q.push(s);dist[s]=0;
	while(!q.empty()){
		int u=q.front();q.pop();inq[u]=0;
		for(int i=head[u];i!=-1;i=edge[i].nxt){
			int v=edge[i].v;
			if(dist[v]>dist[u]+edge[i].c){
				dist[v]=dist[u]+edge[i].c;
				if(!inq[v])inq[v]=1,q.push(v);
			}
		}
	}
}
bool cmp(int x,int y){
	return dist[x]<dist[y];
}
int main(){
	memset(head,-1,sizeof(head));
	cin>>n>>m>>s>>t;
	for(int i=1;i<=m;i++){
		int u,v,c;read(u),read(v),read(c);
		add_edge(u,v,c);
		add_edge(v,u,c);
	}
	spfa();
	for(int i=1;i<=n;i++) p[i]=i;
	sort(p+1,p+n+1,cmp);
	f[s]=1;
	for(int i=1;i<=n;i++){
		int x=p[i];
		for(int j=head[x];j!=-1;j=edge[j].nxt)
			if(dist[edge[j].v]==dist[x]+edge[j].c)
				f[edge[j].v]=(f[edge[j].v]+f[x])%mod;
	}
	g[t]=1;
	for(int i=1;i<=n;i++){
		int x=p[n-i+1];
		for(int j=head[x];j!=-1;j=edge[j].nxt)
			if(dist[edge[j].v]==dist[x]-edge[j].c)
				g[edge[j].v]=(g[edge[j].v]+g[x])%mod;
	}
	ans=f[t]*f[t]%mod;
	for(int i=1;i<=n;i++){
		int x=i;
		for(int j=head[x];j!=-1;j=edge[j].nxt)
			if(dist[edge[j].v]==dist[x]+edge[j].c){
				if((dist[edge[j].v]<<1)>dist[t]&&(dist[x]<<1)<dist[t]){
					ans=((ans-f[x]*g[edge[j].v]%mod*f[x]%mod*g[edge[j].v])%mod+mod)%mod;
				}
			}
	}
	for(int i=1;i<=n;i++)
		if((dist[i]<<1)==dist[t])
			ans=((ans-f[i]*f[i]%mod*g[i]%mod*g[i])%mod+mod)%mod;
	printf("%lld\n",ans);
	return 0;
}