題目#
題解#
看題目範圍，$n\leq100$，又要求最短路，因此考慮 floyd
先預處理出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;
}