记录编号	424681	评测结果	AAAAAAAAAA
题目名称	[NOI 2007]社交网络	最终得分	100
用户昵称	HeHe	是否通过	通过
代码语言	C++	运行时间	0.030 s
提交时间	2017-07-13 22:53:00	内存使用	0.75 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

inline char getc(void) { 
    static char buf[1 << 18], *fs, *ft;
    return (fs == ft && (ft = (fs = buf) + fread(buf, 1, 1 << 18, stdin)), fs == ft) ? EOF : *fs++;
}

inline int read(void) { 
    register int res = 0;
    register char tmp = getc();
    while(!isdigit(tmp)) tmp = getc();
    while(isdigit(tmp))
        res = ((res + (res << 2)) << 1) + (tmp ^ 48),
        tmp = getc();
    return res;
}

double dis[110][110], path[110][110];
int N, M;

int main() { 
#ifndef LOCAL
    freopen("network1.in", "r", stdin);
    freopen("network1.out", "w", stdout);
#endif
    memset(dis, 0x6f, sizeof(dis));
    N = read(), M = read();

    for(int i = 1; i <= N; ++i) dis[i][i] = 0;
    for(int i = 1, a, b; i <= M; ++i) { 
        a = read(), b = read();
        dis[a][b] = dis[b][a] = read();
        path[a][b] = path[b][a] = 1;
    }

    for(int k = 1; k <= N; ++k) { 
        for(int i = 1; i <= N; ++i) { 
            if(k == i) continue;
            for(int j = 1; j <= N; ++j) { 
                if(k == j || i == j) continue;
                if(dis[i][j] > dis[i][k] + dis[k][j]) { 
                    dis[i][j] = dis[i][k] + dis[k][j];
                    path[i][j] = path[i][k] * path[k][j];
                } else if(dis[i][j] == dis[i][k] + dis[k][j]) { 
                    path[i][j] += path[i][k] * path[k][j];
                }
            }
        }
    }

    for(int k = 1; k <= N; ++k) { 
        double ans = 0;
        for(int i = 1; i <= N; ++i) { 
            if(k == i) continue;
            for(int j = i + 1; j <= N; ++j) { 
                if(k == j) continue;
                if(dis[i][j] == dis[i][k] + dis[k][j]) { 
                    ans += path[i][k] * path[k][j] * 1.0 / path[i][j];
                }
            }
        }
        printf("%.3lf\n", ans * 2);
    }
    return 0;
}