解题：NOI 2007 社交网络

 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\n",ans[i]);
41     return 0;
42 }