jiry_2's Blog

两个弗洛伊德+乘法原理，第二个弗洛伊德居然写错了。。调了半天才调出来，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.