记录编号	403458	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]社交网络	最终得分	100
用户昵称	再见	是否通过	通过
代码语言	C++	运行时间	0.071 s
提交时间	2017-05-10 13:52:04	内存使用	0.93 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
typedef long long LL;

int n,m,tot,head[110],next[10010],to[10010],val[10010];
int dis[110],Q[100100],qhead,tail,inq[110],sdisv[110][110];
LL stov[110][110],cnt[110];

void add(int u,int v,int w){
	++tot; to[tot]=v; val[tot]=w;
	next[tot]=head[u]; head[u]=tot;
}

void SPFA(int s){
	memset(dis,0x7f,sizeof(dis));
	memset(cnt,0,sizeof(cnt));
	memset(inq,0,sizeof(inq));
	cnt[s]=1; dis[s]=0;
	for(int i=1;i<=n;i++){
		int u=0;
		for(int j=1;j<=n;j++){
			if(!inq[j]&&!u) u=j;
			if(dis[u]>dis[j]&&!inq[j]) u=j;
		}
		inq[u]=true;
		for(int p=head[u];p;p=next[p])
			if(dis[to[p]]>dis[u]+val[p]){
				dis[to[p]]=dis[u]+val[p];
				cnt[to[p]]=cnt[u];
			}
			else if(dis[to[p]]==dis[u]+val[p])
				cnt[to[p]]+=cnt[u];
	}
}

int main(){
	//freopen("in.in","r",stdin);
	freopen("network1.in","r",stdin);
	freopen("network1.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int x,y,z; scanf("%d%d%d",&x,&y,&z);
		add(x,y,z); add(y,x,z);
	}
	for(int i=1;i<=n;i++){
		SPFA(i);
		for(int j=1;j<=n;j++){
			stov[i][j]=cnt[j];
			sdisv[i][j]=dis[j];
		}
	}
	for(int v=1;v<=n;v++){
		double ans=0;
		for(int s=1;s<=n;s++)
			for(int t=1;t<=n;t++)
				if(s!=v&&t!=v&&s!=t&&sdisv[s][v]+sdisv[v][t]==sdisv[s][t])
					ans+=(double)stov[s][v]*stov[v][t]/(double)stov[s][t];
		printf("%.3lf\n",ans);
	}
	return 0;
}