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