记录编号	79264	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]社交网络	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.040 s
提交时间	2013-11-05 11:36:51	内存使用	0.47 MiB

#include<iostream>
#include<cstdio>
using namespace std;
const double INF=0xffffff;
const int SIZE=101;
double dis[SIZE][SIZE]={0},path[SIZE][SIZE]={0};//两点间最短距和条数
int n,m;
void init(void){
	int i,j;
	scanf("%d%d",&n,&m);
	for(i=0;i<n;i++){
		for(j=0;j<n;j++) dis[i][j]=INF,path[i][j]=1;
		dis[i][i]=0;
	}
	int a,b,c;
	for(i=0;i<m;i++){
		scanf("%d%d%d",&a,&b,&c);
		a--,b--;
		dis[a][b]=dis[b][a]=c;
	}
}
void floyd(void){
	int i,j,k;
	for(k=0;k<n;k++){
		for(i=0;i<n;i++){
			if(i==k) continue;
			for(j=0;j<n;j++){
				if(i==j||j==k) continue;
				if(dis[i][k]+dis[j][k]<dis[i][j]){
					dis[i][j]=dis[i][k]+dis[j][k];
					path[i][j]=path[i][k]*path[j][k];//刷新三观= =
				}
				else if(dis[i][k]+dis[j][k]==dis[i][j]){
					path[i][j]+=path[i][k]*path[j][k];
				}
			}
		}
	}
}
void final(void){
	double temp;
	int i,j,k;
	for(k=0;k<n;k++){
		temp=0;
		for(i=0;i<n;i++){
			if(i==k) continue;
			for(j=0;j<n;j++){
				if(i==j||j==k) continue;
				if(dis[i][k]+dis[k][j]==dis[i][j]){
					temp+=((path[i][k]*path[k][j])/path[i][j]);
				}
			}
		}
		printf("%.3lf\n",temp);
	}
}
int main(){
	freopen("network1.in","r",stdin);
	freopen("network1.out","w",stdout);
	init();
	floyd();
	final();
	return 0;
}