知识点：Floyd+初赛数学水平

 

难点：最短路计数？

 

分析：　　n<=100，每个点都要输出，又和最短路有关

　　　　　“红(chi)果(luo)果(luo)”的告诉你要Floyd啊

　　　　　最短路显然不要说了，看看如何计数：

过两个点的最短路条数：

\begin{matrix} \sum_{k,dis[i][k]+dis[k][j]<dis[i][j]} cnt[i][k]*cnt[k][j] \end{matrix}

　　　　   然后一直更新就好了，看公式难理解的话直接看代码

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #define int long long
 6 using namespace std;
 7 inline int read(){
 8     char chr=getchar();    int f=1,ans=0;
 9     while(!isdigit(chr)) {if(chr=='-') f=-1;chr=getchar();}
10     while(isdigit(chr))  {ans=(ans<<3)+(ans<<1);ans+=chr-'0';chr=getchar();}
11     return ans*f;
12 }int n,m,dis[105][105],cnt[105][105];
13 double ANS[105];
14 #define F for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)
15 signed main(){memset(dis,0x3f,sizeof(dis)),memset(cnt,0,sizeof(cnt));
16     n=read(),m=read();
17     for(int i=1,x,y;i<=m;i++)x=read(),y=read(),dis[x][y]=dis[y][x]=read(),cnt[x][y]=cnt[y][x]=1;
18     F{
19         if(dis[i][j]==dis[i][k]+dis[k][j])
20             cnt[i][j]+=cnt[i][k]*cnt[k][j];
21         if(dis[i][j]>dis[i][k]+dis[k][j])
22             cnt[i][j]=cnt[i][k]*cnt[k][j],dis[i][j]=dis[i][k]+dis[k][j];
23     }F
24         if(i!=j&&i!=k&&k!=j&&dis[i][j]==dis[i][k]+dis[k][j])
25             ANS[k]+=(1.0*cnt[i][k]*cnt[k][j])/cnt[i][j];
26     for(int i=1;i<=n;i++) printf("%0.3lf\n",(ANS[i]));
27     return 0;
28 }