题目
link
题解
看题目范围,n≤100,又要求最短路,因此考虑floyd
先预处理出i
到j
的最短路,顺便还可以求出i
到j
的最短路的条数。具体看代码
统计答案的时候枚举每个点k
,然后枚举s
,t
,如果k
点在s
到t
的最短路上的话,这个点的答案加上cnt[s][k] * cnt[k][t] * 1.0 / cnt[s][t]
不开long long
见祖宗
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| #include<bits/stdc++.h>
using namespace std; int n, m; const int N = 110; int dis[N][N]; long long cnt[N][N]; int main() { ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); cin >> n >> m; memset(dis, 0x3f, sizeof dis); for(int i = 1;i <= n;i++) dis[i][i] = 0, cnt[i][i] = 1; for(int i = 1, a, b, c;i <= m;i++) cin >> a >> b >> c, dis[a][b] = dis[b][a] = c, cnt[a][b] = cnt[b][a] = 1;
for(int k = 1;k <= n;k++) { for(int i = 1;i <= n;i++) { for(int j = 1;j <= n;j++) { if(i == j || i == k || j == k) continue; if(dis[i][k] + dis[k][j] < dis[i][j]) { dis[i][j] = dis[i][k] + dis[k][j]; cnt[i][j] = 0; } if(dis[i][k] + dis[k][j] == dis[i][j]) { cnt[i][j] += cnt[i][k] * cnt[k][j]; } } } } for(int k = 1;k <= n;k++) { double ans = 0; for(int s = 1;s <= n;s++) { for(int t = 1;t <= n;t++) { if(s == k || t == k) continue; if(dis[s][k] + dis[k][t] == dis[s][t]) { ans += cnt[s][k] * cnt[k][t] * 1.0 / cnt[s][t]; } } } printf("%.3lf\n", ans); }
return 0; }
|