先跑一边Floyd乘法原理统计任意两点间最短路数目，然后再枚举一次按照题意即可求出答案，会写那道JSOI2007就会这个
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 using namespace std; 5 const int N=110; 6 long long n,m,t1,t2,t3; 7 long long mat[N][N],cnt[N][N]; 8 double ans[N]; 9 int main () 10 { 11 scanf("%lld%lld",&n,&m); 12 memset(mat,0x3f,sizeof mat); 13 for(int i=1;i<=m;i++) 14 { 15 scanf("%lld%lld%lld",&t1,&t2,&t3); 16 mat[t1][t2]=mat[t2][t1]=t3; 17 cnt[t1][t2]=cnt[t2][t1]=1; 18 } 19 for(int i=1;i<=n;i++) mat[i][i]=0; 20 for(int k=1;k<=n;k++) 21 for(int i=1;i<=n;i++) 22 for(int j=1;j<=n;j++) 23 if(i!=j&&i!=k&&j!=k) 24 { 25 if(mat[i][j]>mat[i][k]+mat[k][j]) 26 { 27 mat[i][j]=mat[i][k]+mat[k][j]; 28 cnt[i][j]=cnt[i][k]*cnt[k][j]; 29 } 30 else if(mat[i][j]==mat[i][k]+mat[k][j]) 31 cnt[i][j]+=cnt[i][k]*cnt[k][j]; 32 } 33 for(int k=1;k<=n;k++) 34 for(int i=1;i<=n;i++) 35 for(int j=1;j<=n;j++) 36 if(i!=j&&i!=k&&j!=k) 37 if(mat[i][k]+mat[k][j]==mat[i][j]) 38 ans[k]+=(double)cnt[i][k]*cnt[k][j]/cnt[i][j]; 39 for(int i=1;i<=n;i++) 40 printf("%.3lf ",ans[i]); 41 return 0; 42 }