問題#
解答#
問題の範囲を見ると、$n\leq100$ であり、最短経路を求める必要があるため、フロイドを考慮します。
まず、iからjへの最短経路を前処理し、ついでにiからjへの最短経路の本数も求めることができます。具体的にはコードを見てください。
答えを集計する際には、各点kを列挙し、次にsとtを列挙します。もしk点がsからtへの最短経路上にある場合、この点の答えにcnt[s][k] * cnt[k][t] * 1.0 / cnt[s][t]を加えます。
long longを開かないで祖先を見よ。
コード#
#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;
}