day6E

题意

正权无向图$G$，有$n$个点与$m$条边。你要回答$q$次询问，每次询问$u,v$两点，回答对于$u,v$两点，这张图上有多少条边在它们任意一条最短路上出现。

数据范围

$$\begin{align*} &1\leq n\leq 500\\ &1\leq m,q\leq n\cdot(n-1)/2\\ &1\leq u,v\leq n\\ &1\leq w\leq 1000 \end{align*} $$

题解

容易想到的做法是，对每次询问，遍历每条边，看这条边是否在$u,v$的最短路上，只需判断d[u] + w == d[v]是否成立即可。但这样的做法是$O(qm)=O(n^4)$的，稳稳的TLE。究其原因，是因为计数的时候不够高效。这种每找到合法边时就+1的策略，可以卡到每次遍历$O(n^2)$条边，举一个例子，对18个点的图，将17放在最左边，18放在最右边，剩下的点从小到大4个一列摆放，然后记17在第一层，1,2,3,4在第二层，…，18在第六层。之后同一层内的点之间不连边，不同层间连一条长为层数差的边，我们就得到了一个$O(n^2)$级别边数，且每条边都在某条最短路上的图。每次都这样询问就会达到复杂度上界。举这个例子不是为了特判这种情况并打表过掉（真的可以吗？），而是为了说明这种对每个点对枚举所有边的做法枚举效率太低了。考虑如何降低到$O(qn)$级别的复杂度。一种想法是，既然定源汇最短路和单源最短路可以同时解决，那么定源汇最短路边数能不能和单源最短路边数同时解决呢？换句话说，一次单源最短路边数的统计结果，能不能想办法应用到不同终点处？最终经过某种思考，对每个指定的$s$，我们将最短路中的边用其终点标记。这句话的想法是，对某个指定的$t$，如果该边终点$v$在$s,t$最短路上，那么由于该边在$s,v$最短路上，而$v,t$最短路是某条$s,t$最短路的一部分，也就一定可以构造一条$s,t$最短路使它包含该边。最终的做法是，对每个源$s$，只沿满足$d[v]=d[u]+w$的边$(u,v)$做某种bfs，这是为了满足拓扑序在前的先遍历，拓扑序在后的后遍历。遍历过程是，每次从堆中取出结点，只沿满足条件的边前进，在终点上计数器+1，若堆中没有终点，将其终点加入按d排列的小顶堆。直至堆为空。最后获取答案$s,t$时，遍历所有点，将每个满足$d[s][u]+d[u][t]$的点u的计数器加到答案中。由于每条边只由其终点标记，这样计数是不重不漏的。成功降低至$O(q,n)$复杂度。

AC代码

#include <bits/stdc++.h>
#define maxn 505
#define inf 100000000005LL
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
vector<pll> G[maxn];
ll d[maxn][maxn], ans[maxn][maxn];
bool vis[maxn][maxn];
void bfs(ll u);
int main()
{
    ll n, m, q, u, v, w;
    ios::sync_with_stdio(false);
    //freopen("2020dlcterm2/day06/E/1.in", "r", stdin);
    //freopen("2020dlcterm2/day06/E/1.out", "w", stdout);
    cin >> n >> m >> q;
    for (ll i = 1; i <= n; i++) {
        for (ll j = 1; j <= n; j++) {
            d[i][j] = i == j ? 0 : inf;
        }
    }
    for (ll i = 1; i <= m; i++) {
        cin >> u >> v >> w;
        G[u].push_back(pll(v, w));
        G[v].push_back(pll(u, w));
        d[u][v] = d[v][u] = w;
    }
    for (ll k = 1; k <= n; k++) {
        for (ll i = 1; i <= n; i++){
            for (ll j = 1; j <= n; j++){
                d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            }
        }
    }
    for (ll i = 1; i <= n; i++){
        bfs(i);
    }
    for (ll i = 1; i <= q; i++)
    {
        cin >> u >> v;
        ll outans = 0;
        for (ll j = 1; j <= n; j++) {
            if(d[u][j] + d[j][v] == d[u][v]) {
                outans += ans[u][j];
            }
        }
        cout << outans << '\n';
        //cout << "u,v:" << u << ' ' << v << ' ' << "d:" << d[u][v] << " ans:" 
        //cout << "vu:" << ans[v][u] << '\n';
    }
    return 0;
}
ll depth[maxn];
struct pt{
    ll d, id;
    bool operator<(const pt& pt2) const {
        return d < pt2.d;
    }
};
priority_queue<pt> que;
void bfs(ll u)
{
    ans[u][u] = -1;
    que.push(pt{-d[u][u], u});
    pt tmp;
    //cout << "bfs:" << u << endl;
    while(!que.empty())
    {
        tmp = que.top();
        que.pop();
        ans[u][tmp.id]++;
        if(vis[u][tmp.id]) {
            continue;
        }
        vis[u][tmp.id] = true;
        //if(tmp.fencha)
        //cout << tmp.id << ' ' << tmp.cnte << ' ' << tmp.fencha << endl;
        //ll cntson = 0;
        for (auto e : G[tmp.id])
        {
            if(d[u][tmp.id] + e.second == d[u][e.first]) {
                que.push(pt{-d[u][e.first], e.first});
            }
        }
    }
}