自动搬运

查看原文

来自洛谷，原作者为

	hellhell 路漫漫其修远兮 吾将上下而求索

搬运于2025-08-24 22:20:34，当前版本为作者最后更新于2021-05-02 10:59:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目大意

题面已经很简洁了，这里不再赘述。

思路分析

定理1：对于一条最短路 $u$ -> $v$，它的任意一个子路径 $u_1$ -> $v_1$ 都是一条最短路。

证明：假设 $u_1$ -> $v_1$ 不是最短路，那么一定可以找到一条路径 $u_2$ -> $v_2$ 使得 $u$ -> $v$ 更短，与 $u$ -> $v$ 是最短路矛盾。

根据定理1，一张图 $G$，在固定源点 $S$ 时，可以得到一张子图 $G_1$ 使得 $G_1$ 上任意一条边都在 $S$ 到至少一个点的最短路径上，且不再 $G_1$ 上的边都不在 $S$ 到任意一个点的最短路上。我们称图 $G_1$ 为最短路图。

判断一条边是否在最短路图上，只需判断 $dis[u]+val[v] == dis[v]$ 是否成立。

求最短路图可以用 SPFA 来解决。

$dis[i]$ 表示距离，$vis[i]$ 表示是否入队，$book[i]$ 表示是否在最短路图中。

void spfa(int s){
    memset(dis,0x3f,sizeof(dis));
    memset(vis,false,sizeof(vis));
    memset(book,false,sizeof(book));
    dis[s]=0;
    vis[s]=true;
    q.push(s);
    while(!q.empty()){
        int now=q.front();
        vis[now]=false;
        q.pop();
        for(int i=head[now];i;i=edge[i].next){
            int v=edge[i].to;
            if(dis[v]>dis[now]+edge[i].val){
                dis[v]=dis[now]+edge[i].val;
                if(!vis[v]){
                    vis[v]=true;
                    q.push(v);
                }
            }
        }
    }
    for(int i=1;i<=m;i++){
        if(dis[edge[i].from]+edge[i].val==dis[edge[i].to])
            book[i]=true;
    }
}

定理2：任意的最短路图，一定不存在环。

证明：假设图中存在环 $u_1$ -> $u_2$ -> $u_3$ -> …… -> $u_n$ -> $u_1$，则有 $dis[u_1]+val[u_2] == dis[u_2]$，$dis[u_2]+val[u_3] == dis[u_3]$，

……

$dis[u_n]+val[u_1] == dis[u_1]$。

因为边权都为正数，则有 $dis[u_n]>dis[u_1]$，$dis[u_1]>dis[u_n]$。 矛盾。

求出最短路图后，考虑如何统计答案。

设 cnt1[i] 表示 $S$ 到 $i$ 点的最短路数量，cnt2[i] 表示 $i$ 点到终点的最短路数量。

那么对于一条边 $e(u,v)$，根据乘法原理，答案为 $cnt1[u]*cnt2[v]$。

但题目中源点和终点并没有给出，只枚举源点，并不能知道终点。根据定理2可以考虑对最短路图拓扑排序，然后按照拓扑序倒序求 $cnt2$。

具体来说，枚举顺序为拓扑序倒序，当前点为 $u$，$u$ 点指向 $v_1$，$v_2$，则有 $cnt2[u]=cnt2[v_1]+cnt2[v_2]$。

$topo$ 数组与 $tag$ 记录拓扑序。

void TopoSort(int s){
    memset(ind,0,sizeof(ind));
    memset(cnt1,0,sizeof(cnt1));
    memset(cnt2,0,sizeof(cnt2));
    cnt1[s]=1;
    q.push(s);
    tag=0;
    for(int i=1;i<=m;i++){
        if(book[i])
            ind[edge[i].to]++;
        
    }
    while(!q.empty()){
        int now=q.front();
        q.pop();
        topo[++tag]=now;
        for(int i=head[now];i;i=edge[i].next){
            if(!book[i])
                continue;
            int v=edge[i].to;
            ind[v]--;
            if(ind[v]==0)
                q.push(v);
            cnt1[v]+=cnt1[now];
            cnt1[v]%=mod;
        }
    }
    for(int i=tag;i;i--){
        int now=topo[i];
        cnt2[now]++;
        for(int j=head[now];j;j=edge[j].next){
            if(!book[j])
                continue;
            int v=edge[j].to;
            cnt2[now]+=cnt2[v];
            cnt2[now]%=mod;
        }
    }
}