果然自己想出来和看题解做出来是完全不同的感觉……
首先考虑没有不相遇的限制条件怎么做。发现这个问题就是 P1144 再加上乘法原理。
然后思考如何处理相遇的情况。容易想到枚举相遇的点和边。首先从 \(s\) 和 \(t\) 开始各跑一遍最短路，\(dis_{u,0/1},cnt_{u,0/1}\) 分别为点 \(u\) 到点 \(s/t\) 的距离和此时的最短路数。
然后考虑如何计算经过点 \(x\) 的最短路数量。这条最短路一定可以分成以下两段：\(s\rightarrow x,x\rightarrow t\)。按照乘法原理，数量即为 \(cnt_{x,0}\times cnt_{x,1}\)。两人同时走过 \(x\) 点的情况数即为这个数的平方。
在边上相遇的情况类似，因为要求一定要经过这条边，读者可自行思考或参考代码。
最后考虑什么时候会相遇。容易想到，对于点，当 \(dis_{u,0}\times 2=dis_{t,0}\) 时会在该点相遇；对于边，当 \(dis_{u,0}\times 2<dis_{t,0}\land dis_{v,1}\times 2<dis_{t,0}\)（说明最短路长的一半在这条边上）且 \(dis_{u,0}+D_i+dis_{v,1}=dis_{t,0}\)（说明该路径为最短路）时会相遇。
将所有情况数减去不合法，即会相遇的方案数即可。
code：
点击查看代码
int n,m,s,t,cnt[N][2];
ll dis[N][2];
bool vis[N];
int tot,head[N];
struct node{
int to,nxt,cw;
}e[N<<2];
priority_queue<pair<ll,int>> q;
inline void add(int u,int v,int w){
e[++tot]={v,head[u],w};
head[u]=tot;
}
void dij(int S,int op){
mems(vis,false);
dis[S][op]=0;
cnt[S][op]=1;
q.push(Mp(0,S));
while(q.size()){
int u=q.top().se;
q.pop();
if(vis[u])
continue;
vis[u]=true;
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(vis[v]||dis[v][op]<dis[u][op]+e[i].cw)
continue;
if(dis[v][op]>dis[u][op]+e[i].cw){
cnt[v][op]=cnt[u][op];
dis[v][op]=dis[u][op]+e[i].cw;
q.push(Mp(-dis[v][op],v));
}else if(dis[v][op]==dis[u][op]+e[i].cw)
cnt[v][op]=(cnt[v][op]+cnt[u][op])%mod;
}
}
}
void solve(){
scanf("%d%d%d%d",&n,&m,&s,&t);
for(int i=1,u,v,w;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
add(u,v,w);
add(v,u,w);
}
mems(dis,0x3f);
dij(s,0);
dij(t,1);
ll d=dis[t][0];
int ans=1ll*cnt[t][0]*cnt[t][0]%mod;
for(int u=1;u<=n;u++){
if(dis[u][0]*2==d)
ans=(ans-1ll*cnt[u][0]*cnt[u][0]%mod*cnt[u][1]%mod*cnt[u][1]%mod+mod)%mod;
else{
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].to;
if(dis[u][0]+e[i].cw+dis[v][1]==d&&dis[u][0]*2<d&&dis[v][1]*2<d)
ans=(ans-1ll*cnt[u][0]*cnt[u][0]%mod*cnt[v][1]%mod*cnt[v][1]%mod+mod)%mod;
}
}
}
printf("%d\n",ans);
}
signed main(){
int t=1;
// scanf("%d",&t);
while(t--)
solve();
}