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;
}