记录编号	185052	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]社交网络	最终得分	100
用户昵称	forever	是否通过	通过
代码语言	C++	运行时间	0.171 s
提交时间	2015-09-04 14:56:57	内存使用	0.33 MiB

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
using namespace std;
long long f[102][102],g[102][102];
int n,m,q,w,e;
int main(){
    freopen("network1.in","r",stdin);
    freopen("network1.out","w",stdout);
   scanf("%d%d",&n,&m);
   for(int i=1;i<=n;++i)
    for(int j=1;j<=n;++j)
	 f[i][j]=999999;
   for(int i=1;i<=m;++i){
		scanf("%d%d%d",&q,&w,&e);
		f[q][w]=f[w][q]=e;
		g[q][w]=g[w][q]=1;
   }
   for(int k=1;k<=n;++k)
	for(int i=1;i<=n;++i)
	 for(int j=1;j<=n;++j){
		if(i==k||j==k||i==j) continue;
	    if(f[i][j]>f[i][k]+f[k][j]){
			f[i][j]=f[i][k]+f[k][j];
			g[i][j]=g[i][k]*g[k][j];
	    }
	    else
		 if(f[i][j]==f[i][k]+f[k][j])
		  g[i][j]+=g[i][k]*g[k][j];
	 }
	 for(int k=1;k<=n;++k){
		double ans=0.00;
		for(int i=1;i<=n;++i)
		 for(int j=1;j<=n;++j){
		   if(i==j||i==k||j==k) continue;
		   if(f[i][j]==f[i][k]+f[k][j]){
				ans+=(double)g[i][k]*g[k][j]/g[i][j];
		   }
		 }
		 printf("%.3lf\n",ans);
	 }
}