题解: Floyd 应用
d[i][j] 两点最短路
c[i][j] 两点最短路条数
转移
若 d[i][k]+d[k][j]<d[i][j] 则 c[i][j]=c[i][k]*c[k][j]
若 d[i][k]+d[k][j]==d[i][j] 则 c[i][j]+=c[i][k]*c[k][j];
统计答案时当 d[s][v]+d[v][t]==d[s][t] 则对答案有贡献 c[s][v]*c[v][t]/c[s][t]
- #include<iostream>
- #include<cstdio>
- #include<cstring>
- using namespace std;
- const int maxn=109;
- const int oo=1000000000;
- int n,m;
- int d[maxn][maxn];
- long long c[maxn][maxn];
- int main(){
- scanf("%d%d",&n,&m);
- for(int i=1;i<=n;++i){
- for(int j=1;j<=n;++j){
- d[i][j]=oo;
- }
- }
- for(int i=1;i<=n;++i)d[i][i]=0;
- while(m--){
- int x,y,z;
- scanf("%d%d%d",&x,&y,&z);
- d[x][y]=d[y][x]=z;
- c[x][y]=c[y][x]=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(d[i][k]+d[k][j]<d[i][j]){
- d[i][j]=d[i][k]+d[k][j];
- c[i][j]=c[i][k]*c[k][j];
- }else if(d[i][k]+d[k][j]==d[i][j]){
- c[i][j]+=c[i][k]*c[k][j];
- }
- }
- }
- }
- for(int k=1;k<=n;++k){
- double ans=0;
- for(int i=1;i<=n;++i){
- for(int j=1;j<=n;++j){
- if((i==j)||(i==k)||(j==k))continue;
- if(d[i][k]+d[k][j]==d[i][j]){
- ans+=1.0*c[i][k]*c[k][j]/c[i][j];
- }
- }
- }
- printf("%.3f\n",ans);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2508240.html