题目

link

题解

看题目范围，$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;
}