直接弗洛伊德记录两个点之间的路径数量就行

#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdio>
#define N 105
#define int long long
using namespace std;
bool Test_MLE_start;
int _=1,n,m,dis[N][N],cnt[N][N];
double ans[N];
inline int reads(){
	char c=getchar();
	int sum=0,f=1;
	while(!isdigit(c)){
		if(c=='-') f=-1;
		c=getchar();
	}
	while(isdigit(c)){
		sum=(sum<<3)+(sum<<1)+(c^'0');
		c=getchar();
	}
	return sum*f;
}
inline void files(){
	freopen("B.in","r",stdin);
	freopen("std.out","w",stdout);
}
inline void clr(){
//	Don't forget!

}
bool Test_MLE_end;
signed main(){
//	printf("%lf Mb\n",(&Test_MLE_end-&Test_MLE_start-1)/1024.0/1024.0);
//	files();
//	_=reads();
	while(_--){
		clr();n=reads(),m=reads();memset(dis,0x3f,sizeof(dis));
		for(int i=1;i<=m;i++){
			int u,v,w;u=reads(),v=reads(),w=reads();
			dis[u][v]=dis[v][u]=min(dis[u][v],w);cnt[u][v]=cnt[v][u]=1;
		}
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(i==k||j==k) continue;
					if(dis[i][j]>dis[i][k]+dis[k][j]){
						dis[i][j]=dis[i][k]+dis[k][j];
						cnt[i][j]=cnt[i][k]*cnt[k][j];
					}
					else if(dis[i][j]==dis[i][k]+dis[k][j]) cnt[i][j]+=cnt[i][k]*cnt[k][j];
				}
			}
		}
//		cout<<"ok\n";
		for(int k=1;k<=n;k++){
			for(int i=1;i<=n;i++){
				for(int j=1;j<=n;j++){
					if(j==k||i==k) continue;
					if(dis[i][k]+dis[k][j]==dis[i][j]) ans[k]+=cnt[i][k]*cnt[k][j]*1.0/cnt[i][j];
				}
			}
		}
		for(int i=1;i<=n;i++) cout<<fixed<<setprecision(3)<<ans[i]*0.5<<"\n";
	}
	return 0;
}

和 P2047 几乎一样