Floyd 同时维护最短距离和路径数，再按经过节点的路径比例计算重要度。
OJ: luogu
题目 ID: P2047
难度:提高
标签:Floyd最短路计数中心性python
日期: 2026-07-17 03:00
题意
对每个节点，累加所有有序端点对的最短路经过该节点的比例。
思路
Floyd 松弛时同时维护 dist[s][t] 和最短路条数 count[s][t]：更短则覆盖，等长则累加。若 dist[s][t]=dist[s][v]+dist[v][t]，经过 v 的最短路数是两段条数乘积，据此累加比例。
Python 知识
- Python 整数自动承载最多
10^10的路径数。 - 二维列表分别保存距离和计数，公式对应清楚。
f"{importance:.3f}"按要求输出三位小数。
代码
python
import sys
input = sys.stdin.buffer.readline
n, edges = map(int, input().split())
infinity = 10**18
distance = [[infinity] * n for _ in range(n)]
paths = [[0] * n for _ in range(n)]
for node in range(n):
distance[node][node] = 0
for _ in range(edges):
u, v, weight = map(int, input().split())
u -= 1
v -= 1
distance[u][v] = distance[v][u] = weight
paths[u][v] = paths[v][u] = 1
for middle in range(n):
for start in range(n):
if start == middle:
continue
for end in range(n):
if end == middle or start == end:
continue
candidate = distance[start][middle] + distance[middle][end]
if candidate < distance[start][end]:
distance[start][end] = candidate
paths[start][end] = paths[start][middle] * paths[middle][end]
elif candidate == distance[start][end]:
paths[start][end] += paths[start][middle] * paths[middle][end]
for node in range(n):
importance = 0.0
for start in range(n):
if start == node:
continue
for end in range(n):
if end != node and end != start and distance[start][end] == distance[start][node] + distance[node][end]:
importance += paths[start][node] * paths[node][end] / paths[start][end]
print(f"{importance:.3f}")原有 C++ 版本仍保留：
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100 + 5;
const long long INF = (1LL << 60);
int n, m;
long long dist_arr[MAXN][MAXN];
long long cnt_arr[MAXN][MAXN];
long double answer[MAXN];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) {
dist_arr[i][j] = 0;
cnt_arr[i][j] = 1;
}
else {
dist_arr[i][j] = INF;
cnt_arr[i][j] = 0;
}
}
answer[i] = 0;
}
for (int i = 1; i <= m; i++) {
int u, v;
long long w;
cin >> u >> v >> w;
if (w < dist_arr[u][v]) {
dist_arr[u][v] = dist_arr[v][u] = w;
cnt_arr[u][v] = cnt_arr[v][u] = 1;
}
else if (w == dist_arr[u][v]) {
cnt_arr[u][v]++;
cnt_arr[v][u]++;
}
}
// Floyd + 最短路条数统计。
// 如果经过 k 更短，就替换距离和条数；
// 如果经过 k 一样短，就把这部分方案数加上。
// 这里跳过 i==k 或 j==k，避免用到 dist[i][i] 这类平凡路径时重复计数。
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
if (i == k) {
continue;
}
for (int j = 1; j <= n; j++) {
if (j == k || i == j) {
continue;
}
long long nd = dist_arr[i][k] + dist_arr[k][j];
long long ways = cnt_arr[i][k] * cnt_arr[k][j];
if (nd < dist_arr[i][j]) {
dist_arr[i][j] = nd;
cnt_arr[i][j] = ways;
}
else if (nd == dist_arr[i][j]) {
cnt_arr[i][j] += ways;
}
}
}
}
// 如果 v 在 s 到 t 的最短路上，那么一定满足：
// dist[s][v] + dist[v][t] == dist[s][t]
// 此时经过 v 的最短路条数就是 cnt[s][v] * cnt[v][t]。
for (int v = 1; v <= n; v++) {
for (int s = 1; s <= n; s++) {
if (s == v) {
continue;
}
for (int t = 1; t <= n; t++) {
if (t == v || t == s) {
continue;
}
if (dist_arr[s][v] + dist_arr[v][t] == dist_arr[s][t]) {
answer[v] += (long double) cnt_arr[s][v] * cnt_arr[v][t] / cnt_arr[s][t];
}
}
}
}
cout << fixed << setprecision(3);
for (int i = 1; i <= n; i++) {
cout << (double) answer[i] << '\n';
}
return 0;
}复杂度
Floyd 和重要度统计均为 O(n^3)，空间 O(n^2)。
总结
最短路计数与 Floyd 同步更新后，节点经过比例可由两段方案数相乘得到。
