Solution
一道不错的计数题。因为直接求不相遇的方案十分复杂，所以考虑正难则反，用总的方案数减去相遇的方案数。求方案数很套路：在求最短路的时候开一个数组 \(del\) 记录到达点 \(i\) 的最短路条数，更新最短路时顺便更新即可。
跑完最短路后，设 \(dis1\) 为 \(s\) 到 \(t\) 的最短路数组，\(del1\) 为 \(s\) 到 \(t\) 的最短路的条数的数组，\(dis2\) 和 \(del2\) 同理，易得总的方案数为 \({del_t}^2\)，接下来考虑求相遇的方案数，共分为两种情况：
-
在点上相遇。设 \(i\) 为相遇点，那么有 \(dis1_i=dis2_i\)，且 \(dis1_i+dis2_i=dis1_t\)，方案数为 \({del1_i}^2 \times {del2_i}^2\)。
-
在边上相遇，设在 \(i\) 边上相遇，且连接 \(u\)，\(v\)，边权为 \(w\)，那么有 \(dis1_u+dis2_v+w=dis1_t\)，且 \(dis1_u+w>dis2_v\)，以及 \(dis2_v+w>dis1_u\)，方案数为 \({del1_i}^2 \times {del2_i}^2\)。
最后输出答案。注意取模。
// Celestial Cyan
// Luogu uid : 706523
// Luogu : https://www.luogu.com.cn/problem/AT_arc090_c
// CF :
// AT : https://www.luogu.com.cn/remoteJudgeRedirect/atcoder/arc090_c
// FTOJ :
// Contest : AtCoder Regular Contest 090
// Cnblogs :
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 2023/8/1
#include<bits/stdc++.h>
#define int long long
#define x first
#define y second
#define il inline
#define db double
#define low(x) x&-x
#define ls(x) x<<1
#define rs(x) x<<1|1
#define pb(x) push_back(x)
#define gcd(x,y) __gcd(x,y)
#define lcm(x,y) x*y/gcd(x,y)
#define debug() puts("-------")
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> PII;
const int N=1e5+10,M=2e5+10,Mod=1e9+7,INF=1e9+7;
int n,m;
int s,t;
int h[N],idx=0;
bool st1[N],st2[N];
int u[N],v[N],w[N];
int dis1[N],dis2[N];
int del1[N],del2[N];
struct Node{
int w;
int to,ne;
}tr[M<<1];
struct Mind{
il bool operator<(Mind &Cyan)const{ }
};
il int read(){
int x=0,f=1; char c=getchar();
while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); }
while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-48; c=getchar(); }
return x*f;
}
il void add(int u,int v,int w){
tr[idx].w=w,tr[idx].to=v,tr[idx].ne=h[u],h[u]=idx++;
}
il void dij1(){
priority_queue<pii> q; q.push({0,s});
memset(st1,false,sizeof st1);
for(int i=1;i<=n;i++) dis1[i]=INF; dis1[s]=0; del1[s]=1;
while(!q.empty()){
int u=q.top().y; q.pop();
if(st1[u]) continue; st1[u]=true;
for(int i=h[u];i!=-1;i=tr[i].ne){
int to=tr[i].to;
if(dis1[to]>dis1[u]+tr[i].w){
dis1[to]=dis1[u]+tr[i].w;
del1[to]=del1[u]; q.push({-dis1[to],to});
} else if(dis1[to]==dis1[u]+tr[i].w) del1[to]=(del1[to]+del1[u])%Mod;
}
}
}
il void dij2(){
priority_queue<pii> q; q.push({0,t});
memset(st2,false,sizeof st2);
for(int i=1;i<=n;i++) dis2[i]=INF; dis2[t]=0; del2[t]=1;
while(!q.empty()){
int u=q.top().y; q.pop();
if(st2[u]) continue; st2[u]=true;
for(int i=h[u];i!=-1;i=tr[i].ne){
int to=tr[i].to;
if(dis2[to]>dis2[u]+tr[i].w){
dis2[to]=dis2[u]+tr[i].w;
del2[to]=del2[u]; q.push({-dis2[to],to});
} else if(dis2[to]==dis2[u]+tr[i].w) del2[to]=(del2[to]+del2[u])%Mod;
}
}
}
signed main(){
memset(h,-1,sizeof h);
n=read(),m=read(); s=read(),t=read();
for(int i=1;i<=m;i++){
u[i]=read(),v[i]=read(),w[i]=read();
add(u[i],v[i],w[i]),add(v[i],u[i],w[i]);
} dij1(); dij2(); int ans=del1[t]*del1[t]%Mod; // cout<<ans<<endl;
for(int i=1;i<=n;i++){
if(dis1[i]+dis2[i]==dis1[t]&&dis1[i]==dis2[i]){
ans=(ans-del1[i]*del1[i]%Mod*del2[i]%Mod*del2[i]%Mod)%Mod;
}
} for(int i=1;i<=m;i++){
if(dis1[u[i]]+dis2[v[i]]+w[i]==dis1[t]&&dis1[u[i]]+w[i]>dis2[v[i]]&&dis2[v[i]]+w[i]>dis1[u[i]]){
ans=(ans-del1[u[i]]*del1[u[i]]%Mod*del2[v[i]]%Mod*del2[v[i]]%Mod)%Mod;
} swap(u[i],v[i]);
if(dis1[u[i]]+dis2[v[i]]+w[i]==dis1[t]&&dis1[u[i]]+w[i]>dis2[v[i]]&&dis2[v[i]]+w[i]>dis1[u[i]]){
ans=(ans-del1[u[i]]*del1[u[i]]%Mod*del2[v[i]]%Mod*del2[v[i]]%Mod)%Mod;
}
} printf("%lld\n",(ans%Mod+Mod)%Mod);
return 0;
} /* */