【题解】[HAOI2012] 道路 最短路 计数 luogu – 3644 —quhengyi11

传送门:[HAOI2012] 道路

一句话题意：给定一张有向图，定义一条边的重要程度为有多少条不同的最短路经过它。求每条边的重要程度。

数据范围：点数 $n\leq 1500$，边数 $m\leq 5000$。

首先我们需要挖掘几个最短路的性质：

1. 将一个点到其它所有点的最短路经过的边组成的图是一个有向无环图 (显然，如果有环，则环上存在有一条边不符合条件 $dis[u]+w[i][j]=dis[v]$(但符合条件的边一定满足这个条件)，除非边权等于 $0$，但由题意可知边权不可能为 $0$，那样就有无数条最短路了)
2. 由性质 $1$构造出来的图中任意一条 $path$肯定是最短路 (由定义可知)，因此我们可以在这张新图上进行计数，即一条边 $(u,v)$的贡献为从源点 $s$到 $u$的路径条数 $from[u]$$\times$点 $v$到其它任意一点的路径条数 $to[v]$。然后这道题就成功变成了一道 $noip$题了

然而我最初写挂了 QwQ

$from[u]$可以由拓扑序求出来，初值是 $from[s]=1$，$to[v]$其实用拓扑逆序也能求出来，初值是 $\forall\; v \in G \;to[v]=1$(可以理解成每个点都是终点)

然后我拓扑排序写挂了 QAQ

我曾经学的是 $\Theta(n^2)$的拓扑排序，其实按广搜的思路跑一边就是一个 $\Theta(n+e)$复杂度的东东，我太蠢了不懂得变通 $QwQ$

最后时间复杂度应该是 $\Theta(n\times(kn+(n+e)))$(枚举源点×(spfa+topo_sort))

代码：

#include<bits/stdc++.h>
#define fo(i, a, b) for (int i = (a); i <= (b); ++i)
#define fd(i, a, b) for (int i = (a); i >= (b); --i)
#define N 1505
#define M 5005
#define mod 1000000007
struct edge{
    int to, nxt, w;
}e[M], E[M];
int dis[N], n, m, u, v, w[M], head[N], vis[N], cnt, last[N], in[N], out[N];
int cnt1[N], cnt2[N], tot, que[M << 2], hh, tt, ans[M];
int fr[M], to[M], h1, t1, q[N];
bool fl[N];
inline void init ()
{
    memset(last, 0, sizeof last);
    memset(in, 0, sizeof in);
    memset(out, 0, sizeof out);
    memset(cnt1, 0, sizeof cnt1);
    fo (i, 1, n) cnt2[i] = 1;
}
inline void spfa (int s)
{
    memset(dis, 0x3f, sizeof dis);
    dis[s] = 0;
    hh = tt = 1;
    que[1] = s;
    fl[s] = 1;
    while (hh <= tt)
    {
        int u = que[hh++];
        for (int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].to;
            if (dis[v] > dis[u] + e[i].w)
            {
                dis[v] = dis[u] + e[i].w;
                if (!fl[v])
                {
                    fl[v] = 1;
                    que[++tt] = v;
                }
            }
        }
        fl[u] = 0;
    }
}
int main ()
{
    scanf("%d %d", &n, &m);
    fo (i, 1, m)
    {
        scanf("%d %d %d", &fr[i], &to[i], &w[i]);
        e[++tot] = (edge) {to[i], head[fr[i]], w[i]};
        head[fr[i]] = tot;
    }
    fo (s, 1, n)
    {
        init();
        spfa(s);
        cnt = 0;
        fo (i, 1, m)
        {
            u = fr[i]; v = to[i];
            if (dis[u] + w[i] == dis[v])
            {
                E[++cnt] = (edge) {v, last[u], w[i]};
                last[u] = cnt;
                ++out[u]; ++in[v];
            }
        }
        cnt1[s] = 1; q[1] = s; h1 = 1; t1 = 1;
        while (h1 <= t1)
        {
            u = q[h1++];
            for (int i = last[u]; i; i = E[i].nxt)
            {
                v = E[i].to;
                cnt1[v] += cnt1[u];
                if (!--in[v]) q[++t1] = v;
            }
        }
        fd (i, t1, 1)
        {
            u = q[i];
            for (int i = last[u]; i; i = E[i].nxt)
            {
                v = E[i].to;
                cnt2[u] += cnt2[v];
            }
        }
        fo (i, 1, m)
            if (dis[fr[i]] + w[i] == dis[to[i]])
                ans[i] = (ans[i] + cnt1[fr[i]] * cnt2[to[i]]) % mod;
    }
    fo (i, 1, m)
        printf("%d\n", ans[i]);
    return 0;
}