// luogu-judger-enable-o2
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
#include<map>
#include<cmath>
using namespace std;
const int MAXN = 1e5 + 10, INF = 1e8 + 10;
inline int read() {
char c = getchar(); int x = 0, f = 1;
while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x * f;
}
int N, M;
int dis[101][101], f[101][101], num[101][101][101], w[101][101];
void Floyed() {
for(int k = 1; k <= N; k++) {
dis[k][k] = 0;
for(int i = 1; i <= N; i++)
for(int j = 1; j <= N; j++)
dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
}
}
int GetAns(int bg, int now, int pre) {
int ans = 0;
if(bg == now) return 1;
for(int i = 1; i <= N; i++) {
if(now != i && dis[bg][now] == dis[bg][i] + w[i][now]) {
int x = GetAns(bg, i, pre);
num[bg][pre][i] += x;
ans += x;
}
}
return ans;
}
double ans[MAXN];
main() {
#ifdef WIN32
freopen("a.in", "r", stdin);
//freopen("a.out", "w", stdout);
#endif
N = read(); M = read();
memset(dis, 0x3f, sizeof(dis));
memset(w, 0x3f, sizeof(w));
for(int i = 1; i <= M; i++) {
int x = read(), y = read(), z = read();
w[x][y] = w[y][x] = dis[x][y] = dis[y][x] = z;
}
Floyed();
for(int i = 1; i <= N; i++) {
f[i][i] = 1;
for(int j = 1; j <= N; j++)
f[i][j] = GetAns(i, j, j);
}
for(int i = 1; i <= N; i++) {
double ans = 0;
for(int s = 1; s <= N; s++) {
for(int t = 1; t <= N; t++)
if(s != i && t != i && s != t)
ans += (double)num[s][t][i] / f[s][t];
}
printf("%.3lf\n", ans);
}
return 0;
}
网友评论