传送门
解题思路
概括一下题意：
求所有点两两之间最短路的条数和经过k点的最短路的条数。
可以用Floyd边求边维护。
和Floyd本身一样不是很好感性理解，越深想越感觉可能落下或者多算。
要注意最短路条数f[i][i]不能初始化为1.否则当k==i松弛时会多算。
AC代码
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<iomanip>
using namespace std;
int n,m,ma[105][105];
double f[105][105],ans[105];
int main(){
ios::sync_with_stdio(false);
cin>>n>>m;
memset(ma,0x3f,sizeof(ma));
for(int i=1;i<=n;i++){
ma[i][i]=0;
}
for(int i=1;i<=m;i++){
int u,v,w;
cin>>u>>v>>w;
ma[u][v]=ma[v][u]=w;
f[u][v]=f[v][u]=1;
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int d=ma[i][k]+ma[k][j];
if(ma[i][j]==d){
f[i][j]+=f[i][k]*f[k][j];
}
if(ma[i][j]>d){
ma[i][j]=d;
f[i][j]=f[i][k]*f[k][j];
}
}
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(k==i||k==j) continue;
if(ma[i][j]==ma[i][k]+ma[k][j]) ans[k]+=f[i][k]*f[k][j]/f[i][j];
}
}
cout<<fixed<<setprecision(3)<<ans[k]<<endl;
}
return 0;
}