Problem#
Solution#
Looking at the problem constraints, $n\leq100$, and since we need the shortest path, we consider Floyd.
First, we preprocess the shortest path from i to j, and we can also calculate the number of shortest paths from i to j. See the code for details.
When counting the answer, we enumerate each point k, then enumerate s, t. If point k is on the shortest path from s to t, then the answer for this point is increased by cnt[s][k] * cnt[k][t] * 1.0 / cnt[s][t].
Do not use long long and see the ancestors.
Code#
#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;
}