牛客网：雪拉比的求救（最短路计数）

链接：https://ac.nowcoder.com/acm/contest/7293/I
来源：牛客网

题目描述

爱与正义的火箭队为了得到雪拉比，于是对它展开了捕捉计划。当雪拉比受到伤害时，它会使用全部能力穿越到1小时之后的时间，并发出了SOS的求救。
小梁在旅行的途中感受到了雪拉比的求救，她跟着雪拉比的求救，来到了一座遗迹，该遗迹的俯视图可看为

ext{d}_idi​。 通过心灵指引小梁终于救出了雪拉比。但是由于被火箭队追赶，雪拉比只能隐藏自己的气息。 火箭队也发现了雪拉比和小梁的位置，同时小梁也在雪拉比的帮助下确定了火箭队的位置。小梁想知道在她和火箭队移动速度相同的条件下，为了顺利的躲避火箭队，并且双方都以最短路径向对方原始位置移动，有多少方案可以使得他们不相遇，并对方案数取模109+710^9+7109+7。

//由于双方只会选择最短路
//先处理出每个点到s的最短路距离和到t的最短路距离
//每个点到s的最短路数量和到t的最短路数量
//如果两个距离之和不等于s到t的最短路，就不算贡献
//如果在点上相遇
//需要满足这个点两边的最短路长度相同
//答案是两边的最短路数量平方的乘积
//如果在边上相遇
//枚举每个点和它的令接点
//如果这个点到s的最短路加上这个点到t的最短路的和加上这条边的边权等于st的最短路
//再看这两条路径的差是否小于等于这条边权
//如果前面条件全都符合，对答案的贡献是两边最短路数量平方的乘积

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1e5+100;
const int mod=1e9+7;
const ll inf=1e18;
int n,m,s,t;
struct node {
    int u,v,w,nxt;
}edge[maxn*4];
int head[maxn];
int tot;
void addedge (int u,int v,int w) {
    edge[tot].u=u;
    edge[tot].v=v;
    edge[tot].w=w;
    edge[tot].nxt=head[u];
    head[u]=tot++;
    
} 
ll d[2][maxn];
ll cnt[2][maxn];
int vis[maxn];
struct qnode {
    ll v;
    ll w;
    bool operator < (const qnode &r) const {
        return w>r.w;
    }
    qnode (int vv,ll ww) {
        v=vv;
        w=ww;
    }
};
void dij (int s,int f) {
    for (int i=0;i<maxn;i++) d[f][i]=inf,vis[i]=0;
    priority_queue<qnode> q;
    d[f][s]=0;
    cnt[f][s]=1;
    q.push(qnode(s,0));
    while (!q.empty()) {
        qnode tt=q.top();
        q.pop();
        int u=tt.v;
        if (vis[u]) continue;
        vis[u]=1;
        for (int i=head[u];i!=-1;i=edge[i].nxt)    {
            int v=edge[i].v;
            int w=edge[i].w;
            if (d[f][v]>d[f][u]+w) {
                d[f][v]=d[f][u]+w;
                cnt[f][v]=cnt[f][u];
                q.push(qnode(v,d[f][v]));
            }
            else if (d[f][v]==d[f][u]+w) 
                cnt[f][v]=(cnt[f][v]+cnt[f][u])%mod;
        }
    }
}
int main () {
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++) head[i]=-1;
    tot=0;
    scanf("%d%d",&s,&t);
    for (int i=1;i<=m;i++) {
        int u,v,w;
        scanf("%d%d%d",&u,&v,&w);
        addedge(u,v,w);
        addedge(v,u,w);
    }
    dij(s,0);
    dij(t,1);
    ll ans=cnt[0][t]%mod*cnt[0][t]%mod;
    ans%=mod;
    for (int i=1;i<=n;i++) {
        if (d[0][i]+d[1][i]!=d[0][t]) continue;
        if (d[0][i]!=d[1][i]) continue;
        ans-=(cnt[0][i]*cnt[1][i]%mod)*(cnt[0][i]*cnt[1][i]%mod)%mod;
        ans=(ans+mod)%mod;
    }
    for (int i=1;i<=n;i++) {
        for (int j=head[i];j!=-1;j=edge[j].nxt) {
            int v=edge[j].v;
            int u=i;
            //printf("%lld
",d[0][u]+d[1][v]+edge[j].w);
            if (d[0][u]+d[1][v]+edge[j].w!=d[0][t])
                continue;
            if (d[0][u]*2<d[0][t]&&d[1][v]*2<d[0][t])
                ans-=(cnt[0][u]*cnt[1][v]%mod)*(cnt[0][u]*cnt[1][v]%mod)%mod,
                ans=(ans+mod)%mod;
        }
    }
    //printf("%lld
",cnt[0][t]*cnt[0][t]);
    printf("%lld
",ans);
    
}

牛客网：雪拉比的求救（最短路计数）

题目描述

题解：