记录编号	10574	评测结果	RRRRRRRRRR
题目名称	[NOI 2007]社交网络	最终得分	0
用户昵称	BYVoid	是否通过	未通过
代码语言	C++	运行时间	0.022 s
提交时间	2009-06-05 10:07:33	内存使用	0.38 MiB

/* 
 * Problem: NOI2007 network
 * Author: Guo Jiabao
 * Time: 2009.6.5 9:54
 * State: Solved
 * Memo: 最短路径
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;
const int MAXN=101;
const double INF=1e20;
int N,M;
double dist[MAXN][MAXN],path[MAXN][MAXN];
void init()
{
	int i,j,a,b,c;
	freopen("network.in","r",stdin);
	freopen("network.out","w",stdout);
	scanf("%d%d",&N,&M);
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			dist[i][j]=INF;
			path[i][j]=1;
		}
		dist[i][i]=0;
	}
	for (i=1;i<=M;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		dist[a][b]=dist[b][a]=c;
	}
}
void floyd()
{
	int i,j,k;
	double I;
	for (k=1;k<=N;k++)
		for (i=1;i<=N;i++)
			for (j=1;j<=N;j++)
			{
				if (i==k || k==j || i==j) continue;
				if (dist[i][k] + dist[k][j] < dist[i][j])
				{
					dist[i][j] = dist[i][k] + dist[k][j];
					path[i][j] = path[i][k] * path[k][j];
				}
				else if (dist[i][k] + dist[k][j] == dist[i][j])
					path[i][j] += path[i][k] * path[k][j];
			}
	for (k=1;k<=N;k++)
	{
		I=0;
		for (i=1;i<=N;i++)
			for (j=1;j<=N;j++)
				if (i!=k && j!=k && i!=j && dist[i][k] + dist[k][j] == dist[i][j])
					I += path[i][k] * path[k][j] / path[i][j];
		printf("%.3lf\n",I);
	}
}
int main()
{
	init();
	floyd();
	return 0;
}