P2505 [HAOI2012] 道路 Solution

Description

给定一张 $n$ 点 $m$ 边的带权有向图 $G$。
对于每条边 $(u_i,v_i,w_i)$，求经过它的最短路径的条数，对 $10^9+7$ 取模.

Limitations

$1\le n\le 1500$
$1\le m\le 3500$
$1\le u,v\le n$
$1\le w\le 10000$

Solution

不难想到暴力：枚举每对 $(s,t)$，统计每个点到 $s$ 和 $t$ 的最短路数量，分别记为 $a_i,b_i$，则对边 $(u,v,w)$ 的贡献为 $a_u{b}_v$，可以拿到 $60\text{pts}$.

接下来优化，我们发现可以只枚举 $s$，并将 $G$ 上不在任何最短路中的边删掉，就会形成一个 DAG，原因显然.
然后在 DAG 上按拓扑序正反跑两次，即可求出 $a_i,b_i$.
使用 Dijkstra，时间复杂度 $O(nm\log n)$.

PS：跑最短路时即可求出 DAG 的拓扑序.

Code

$5.02\text{KB},677\text{ms},680\text{KB}\text{(in total, C++20 with O2)}$
modint 删了.

// Problem: P2505 [HAOI2012] 道路
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2505
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;template<class T>
bool chmax(T &a, const T &b){if(a < b){ a = b; return true; }return false;
}template<class T>
bool chmin(T &a, const T &b){if(a > b){ a = b; return true; }return false;
}template <int MOD>
struct modint {};   // Removed
using Z = modint<1000000007>;
using pii = pair<int, int>;
constexpr int inf = 2e9;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;scanf("%d %d", &n, &m);vector<vector<array<int, 3>>> adj(n);for (int i = 0, u, v, w; i < m; i++) {scanf("%d %d %d", &u, &v, &w);u--, v--;adj[u].push_back({v, w, i});}vector<int> dis(n), dot;vector<bool> vis(n);vector<Z> cnt1(n), cnt2(n), ans(m);auto dij = [&](int s) {fill(cnt1.begin(), cnt1.end(), 0);fill(dis.begin(), dis.end(), inf);fill(vis.begin(), vis.end(), false);dot.clear();priority_queue<pii, vector<pii>, greater<pii>> pq;pq.emplace(0, s);dis[s] = 0;cnt1[s] = 1;while (!pq.empty()) {int u = pq.top().second;pq.pop();if (vis[u]) continue;vis[u] = true;dot.push_back(u);for (auto [v, w, _] : adj[u]) {if (dis[v] > dis[u] + w) {dis[v] = dis[u] + w;cnt1[v] = cnt1[u];pq.emplace(dis[v], v);}else if (dis[v] == dis[u] + w) cnt1[v] += cnt1[u];}}reverse(dot.begin(), dot.end());for (auto u : dot) {cnt2[u] = 1;for (auto [v, w, id] : adj[u])if (dis[u] + w == dis[v]) {cnt2[u] += cnt2[v];ans[id] += cnt1[u] * cnt2[v];}}};for (int i = 0; i < n; i++) dij(i);for (int i = 0; i < m; i++) printf("%d\n", ans[i].val);return 0;
}