两个弗洛伊德+乘法原理,第二个弗洛伊德居然写错了。。调了半天才调出来,QAQ
program p1491; var b,f:array[1..300,1..300] of int64; w:array[1..300] of extended; n,m,i,j,k1,k2,k3,k:longint; begin fillchar(f,sizeof(f),0); fillchar(b,sizeof(b),$3f); readln(n,m); for i:=1 to m do begin readln(k1,k2,k3); if k3<b[k1,k2] then begin b[k1,k2]:=k3; b[k2,k1]:=k3; f[k1,k2]:=1; f[k2,k1]:=1; end; end; for k:=1 to n do for i:=1 to n do for j:=1 to n do begin if (i=j) or (j=k) or (k=i) then continue; if b[i,k]+b[k,j]<b[i,j] then begin b[i,j]:=b[i,k]+b[k,j]; f[i,j]:=f[i,k]*f[k,j]; end else if b[i,k]+b[k,j]=b[i,j] then f[i,j]:=f[i,j]+f[i,k]*f[k,j]; end; fillchar(w,sizeof(w),0); for k:=1 to n do for i:=1 to n do for j:=1 to n do if (i<>k) and (j<>k) and (b[i,k]+b[k,j]=b[i,j])and (i<>j)then w[k]:=w[k]+f[i,k]*f[k,j]/f[i,j]; for i:=1 to n do writeln(w[i]:0:3); end.