noi 2007 社交网络最短路

题意：
大水题一道
 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<cstring>
 5 using namespace std;
 6 #define MAXN 101
 7 int map[MAXN][MAXN];
 8 long long path[MAXN][MAXN];
 9 int c[MAXN][MAXN][MAXN];
10 double ans[MAXN];
11 int n,m;
12 void solve()
13 {
14     memset(ans,0,sizeof(ans));
15     int i,j,k;
16     for(k=1;k<=n;k++)
17         for(i=1;i<=n;i++)
18             for(j=1;j<=n;j++)
19                 if(i!=j&&j!=k&&k!=i)
20                 {
21                     if(map[i][k]+map[k][j]==map[i][j])
22                         ans[k]+=(double)path[i][k]*path[k][j]/path[i][j];
23                 }
24     for(i=1;i<=n;i++)
25         printf("%.3lf\n",ans[i]);
26 }
27  
28 void floyd()
29 {
30     int i,j,k;
31     for(k=1;k<=n;k++)
32         for(i=1;i<=n;i++)
33             for(j=1;j<=n;j++)
34                 if(i!=j&&j!=k&&i!=k)
35                 {
36                     if(map[i][k]+map[k][j]<map[i][j])
37                     {
38                         map[i][j]=map[i][k]+map[k][j];
39                         path[i][j]=path[i][k]*path[k][j];
40                     }
41                     else if(map[i][k]+map[k][j]==map[i][j])
42                         path[i][j]+=path[i][k]*path[k][j];
43                 }
44 }
45 int main()
46 {
47     memset(path,0,sizeof(path));
48     memset(map,0x3f,sizeof(map));
49     int x,y,z;
50     scanf("%d%d",&n,&m);
51     int i;
52     for(i=1;i<=m;i++)
53     {
54         scanf("%d%d%d",&x,&y,&z);
55         map[x][y]=map[y][x]=z;
56         path[x][y]=path[y][x]=1;
57     }
58     floyd();
59     solve();
60     return 0;
61 }
noi 2007 社交网络 最短路

noi 2007 社交网络最短路
