1 /************************************************************** 2     Problem: 1491 3     User: rausen 4     Language: C++ 5     Result: Accepted 6     Time:104 ms 7     Memory:936 kb 8 ****************************************************************/ 9  10 #include <cstdio>11 #include <cstring>12  13 using namespace std;14 typedef long long ll;15 typedef double lf;16 const int N = 105;17  18 int n, m;19 int d[N][N];20 ll cnt[N][N];21 lf ans;22  23 inline int read() {24     int x = 0, sgn = 1;25     char ch = getchar();26     while (ch < ‘0‘ || ‘9‘ < ch) {27         if (ch == ‘-‘) sgn = -1;28         ch = getchar();29     }30     while (‘0‘ <= ch && ch <= ‘9‘) {31         x = x * 10 + ch - ‘0‘;32         ch = getchar();33     }34     return sgn * x;35 }36  37 int main() {38     int i, j, k, x, y, z;39     n = read(), m = read();40     memset(d, 127/3, sizeof(d));41     for (i = 1; i <= m; ++i) {42         x = read(), y = read(), z = read();43         d[x][y] = d[y][x] = z;44         cnt[x][y] = cnt[y][x] = 1;45     }46     for (k = 1; k <= n; ++k)47         for (i = 1; i <= n; ++i) if (i != k)48             for (j = 1; j <= n; ++j) if (j != i && j != k)49                 if (d[i][j] > d[i][k] + d[k][j])50                     d[i][j] = d[i][k] + d[k][j],51                     cnt[i][j] = cnt[i][k] * cnt[k][j];52                 else if (d[i][j] == d[i][k] + d[k][j])53                     cnt[i][j] += cnt[i][k] * cnt[k][j];54     for (k = 1; k <= n; ++k) {55         ans = 0;56         for (i = 1; i <= n; ++i) if (i != k)57             for (j = 1; j <= n; ++j) if (j != i && j != k)58                 if (d[i][j] == d[i][k] + d[k][j])59                     ans += (lf) (cnt[i][k] * cnt[k][j]) /cnt[i][j];60         printf("%.3lf\n", ans);61     }62     return 0;63 }