记录编号	156764	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]社交网络	最终得分	100
用户昵称	Satoshi	是否通过	通过
代码语言	C++	运行时间	0.042 s
提交时间	2015-04-06 10:09:33	内存使用	0.47 MiB

#include <fstream>
#include <algorithm>
#include <iomanip>
using namespace std;
ifstream in("network1.in");
ofstream out("network1.out");
int n,m;
double f[101][101]={0},g[101][101]={0};
double ans[101]={0};
void print(double a)
{
	out<<setprecision(3)<<std::fixed<<a<<endl;
}
int main()
{
	int i,j,k,a,b,c;
	in>>n>>m;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			if(i!=j)
			{
				f[i][j]=9999999;
			}
		}
	}
	for(i=1;i<=m;i++)
	{
		in>>a>>b>>c;
		f[a][b]=c;
		f[b][a]=c;
		g[a][b]=1;
		g[b][a]=1;
	}
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			if(k==i)continue;
			for(j=1;j<=n;j++)
			{
				if(i==j||k==j)continue;
				{
					if(f[i][k]+f[k][j]<f[i][j])
					{
						f[i][j]=f[i][k]+f[k][j];
						g[i][j]=g[i][k]*g[k][j];
					}
					else
					{
						if(f[i][k]+f[k][j]==f[i][j])
						{
							g[i][j]+=g[i][k]*g[k][j];
						}
					}
				}
			}
		}
	}
	for(k=1;k<=n;k++)
	{
		for(i=1;i<=n;i++)
		{
			if(k==i)continue;
			for(j=1;j<=n;j++)
			{
				if(i==j||k==j)continue;
				if(f[i][k]+f[k][j]==f[i][j])
				{
					ans[k]+=(g[i][k]*g[k][j])/g[i][j];
				}
			}
		}
	}
	for(i=1;i<=n;i++)print(ans[i]);
	return 0;
}