传送门

最短路计数问题。因为数据量非常小($N \leq 100$)，所以Floyd随便搞搞就行了。

$f[i][j]$表示路径长度，$g[i][j]$表示最短路方案数。

先跑一遍裸的Floyd，然后利用乘法原理统计$g[i][j]$即可。

$g[i][j]=\sum g[i][k] \times g[k][j]$

//BZOJ 1491//by Cydiater//2016.10.27#include <iostream>#include <cstdlib>#include <cstdio>#include <queue>#include <map>#include <ctime>#include <cmath>#include <cstring>#include <string>#include <algorithm>#include <bitset>#include <iomanip>using namespace std;#define ll long long#define up(i,j,n)		for(int i=j;i<=n;i++)#define down(i,j,n)		for(int i=j;i>=n;i--)#define cmax(a,b) a=max(a,b)#define cmin(a,b) a=min(a,b)#define db doubleconst ll MAXN=105;const ll oo=1LL<<60;inline ll read(){	char ch=getchar();ll x=0,f=1;	while(ch>‘9‘||ch<‘0‘){if(ch==‘-‘)f=-1;ch=getchar();}	while(ch>=‘0‘&&ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}	return x*f;}ll N,M,f[MAXN][MAXN],g[MAXN][MAXN],len=0;db ans[MAXN];struct edge{	ll x,y,v;}e[MAXN*MAXN];namespace solution{	void init(){		N=read();M=read();		up(i,1,N)up(j,1,N)f[i][j]=oo;		up(i,1,N)f[i][i]=0;		memset(g,0,sizeof(g));		up(i,1,M){			ll x=read(),y=read(),v=read();			f[x][y]=f[y][x]=v;			e[++len]=(edge){x,y,v};		}	}	void slove(){		up(k,1,N)up(i,1,N)up(j,1,N)cmin(f[i][j],f[i][k]+f[k][j]);		up(i,1,len){			ll x=e[i].x,y=e[i].y,v=e[i].v;			if(f[x][y]==v)g[x][y]=g[y][x]=1;		}		up(k,1,N)up(i,1,N)up(j,1,N)if(f[i][j]==f[i][k]+f[k][j]&&i!=k&&j!=k){			g[i][j]+=g[i][k]*g[k][j];			//cout<<i<<‘ ‘<<k<<‘ ‘<<j<<‘ ‘<<g[i][k]<<‘ ‘<<g[k][j]<<‘ ‘<<g[i][j]<<endl;		}		up(k,1,N)up(i,1,N)up(j,1,N)if(f[i][j]==f[i][k]+f[k][j]&&i!=k&&k!=j&&i!=j)			ans[k]+=(db)(g[i][k]*g[k][j])/(db)(g[i][j]);	}	void output(){		up(i,1,N)printf("%.3lf\n",ans[i]);	}}int main(){	//freopen("input.in","r",stdin);	using namespace solution;	init();	slove();	output();	return 0;}

BZOJ1491: [NOI2007]社交网络