记录编号	13531	评测结果	EEEEEEEEEE
题目名称	[NOI 2007]社交网络	最终得分	0
用户昵称	maxiem	是否通过	未通过
代码语言	Pascal	运行时间	0.002 s
提交时间	2009-10-06 12:03:49	内存使用	0.32 MiB

program network;
var
  path,dis:array [1..100,1..100] of int64;
  ans:array [1..100] of extended;
  i,n,m,a,b,v:longint;
begin
  fillchar (ans,sizeof(ans),0);
  assign (input,'network.in');
  reset (input);
  readln (n,m);
  for a:=1 to n do for b:=1 to n do begin
    dis[a,b]:=10000000000;
    path[a,b]:=1;
  end;
  for i:=1 to m do begin
    readln (a,b,v);
    dis[a,b]:=v;
    dis[b,a]:=v;
  end;
  close (input);
  assign (output,'network.out');
  rewrite (output);
  for i:=1 to n do for a:=1 to n do for b:=1 to n do if (i<>a) and (i<>b) and (a<>b) then
    if dis[a,b]>dis[a,i]+dis[i,b] then begin
      dis[a,b]:=dis[a,i]+dis[i,b];
      path[a,b]:=path[a,i]*path[i,b];
    end
    else if dis[a,b]=dis[a,i]+dis[i,b] then path[a,b]:=path[a,b]+path[a,i]*path[i,b];
  for i:=1 to n do for a:=1 to n do for b:=1 to n do
    if (a<>i) and (b<>i) and (a<>b) and (dis[a,i]+dis[i,b]=dis[a,b]) and (path[a,b]<>0) then
      ans[i]:=ans[i]+path[a,i]*path[i,b]/path[a,b];
  for i:=1 to n do writeln (ans[i]:0:3);
  close (output);
end.