$n$非常的小，结合题目计算式可以想到$O(n^3)$暴枚$s,t,v$，看$v$在不在$s o t$最短路上（$dis_{s,v}+dis_{v,t}=dis_{s,v}$是$v$在两点最短路上的充要条件——很好证），在则统计$frac{cnt_{s,v} imes cnt_{v,t}}{cnt_{s,t}}$，这个$cnt$就是最短路条数。可以用dij，但是从代码简洁性的角度和出题人的意图，还是用了Floyd来统计，统计原理基本和dij一致。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<cmath> 6 #define dbg(x) cerr << #x << " = " << x <<endl 7 using namespace std; 8 typedef long long ll; 9 typedef double db; 10 typedef pair<int,int> pii; 11 template<typename T>inline T _min(T A,T B){return A<B?A:B;} 12 template<typename T>inline T _max(T A,T B){return A>B?A:B;} 13 template<typename T>inline char MIN(T&A,T B){return A>B?(A=B,1):0;} 14 template<typename T>inline char MAX(T&A,T B){return A<B?(A=B,1):0;} 15 template<typename T>inline void _swap(T&A,T&B){A^=B^=A^=B;} 16 template<typename T>inline T read(T&x){ 17 x=0;int f=0;char c;while(!isdigit(c=getchar()))if(c=='-')f=1; 18 while(isdigit(c))x=x*10+(c&15),c=getchar();return f?x=-x:x; 19 } 20 const int N=100+7; 21 db ans[N]; 22 ll cnt[N][N]; 23 int dis[N][N]; 24 int n,m; 25 26 int main(){//freopen("test.in","r",stdin);//freopen("test.ans","w",stdout); 27 read(n),read(m); 28 memset(dis,0x3f,sizeof dis); 29 for(register int i=1,x,y,z;i<=m;++i)read(x),read(y),read(z),dis[x][y]=dis[y][x]=z,cnt[x][y]=cnt[y][x]=1; 30 for(register int i=1;i<=n;++i)dis[i][i]=0; 31 for(register int k=1;k<=n;++k) 32 for(register int i=1;i<=n;++i) 33 for(register int j=1;j<=n;++j) 34 if(dis[i][j]==dis[i][k]+dis[k][j])cnt[i][j]+=cnt[i][k]*cnt[k][j]; 35 else if(MIN(dis[i][j],dis[i][k]+dis[k][j]))cnt[i][j]=cnt[i][k]*cnt[k][j]; 36 for(register int i=1;i<n;++i) 37 for(register int j=i+1;j<=n;++j) 38 for(register int k=1;k<=n;++k)if(i^k&&j^k&&dis[i][k]+dis[k][j]==dis[i][j]) 39 ans[k]+=(db)cnt[i][k]*cnt[k][j]/cnt[i][j]*2.0; 40 for(register int i=1;i<=n;++i)printf("%.3f ",ans[i]); 41 return 0; 42 }