记录编号	318618	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]社交网络	最终得分	100
用户昵称	liu_runda	是否通过	通过
代码语言	C++	运行时间	0.047 s
提交时间	2016-10-09 19:10:54	内存使用	0.46 MiB

#include<cstdio>
#include<cstring>
typedef long long ll;
const int maxn=105;
ll dis[maxn][maxn],cnt[maxn][maxn];
double ans[maxn]; 
int main(){
    freopen("network1.in","r",stdin);
    freopen("network1.out","w",stdout);
    int n,m;scanf("%d%d",&n,&m);
    memset(dis,0x3f,sizeof(dis));
    int a,b,w;
    for(int i=1;i<=m;++i){
        scanf("%d%d%d",&a,&b,&w);
        dis[a][b]=dis[b][a]=w;
        cnt[a][b]=cnt[b][a]=1;
    }
    for(int i=1;i<=n;++i){
        dis[i][i]=0;
    }
    for(int k=1;k<=n;++k){//只要理解floyd是依次计算出任意两点之间经过编号小于等于k的点的最短路，最短路计数也就很好理解了。 
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(dis[i][k]+dis[k][j]<dis[i][j]){
                    dis[i][j]=dis[i][k]+dis[k][j];
                    cnt[i][j]=cnt[i][k]*cnt[k][j];
                }else if(dis[i][k]+dis[k][j]==dis[i][j]){
                    cnt[i][j]+=cnt[i][k]*cnt[k][j];
                }
            }
        }   
    }
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(i!=k&&k!=j&&dis[i][k]+dis[k][j]==dis[i][j]){
                    ans[k]+=cnt[i][k]*1.0*cnt[k][j]/cnt[i][j];
                }
            }
        }
    }
    for(int i=1;i<=n;++i){
        printf("%.3f\n",ans[i]);
    }
    fclose(stdin);fclose(stdout);
    return 0;
}