记录编号 380627 评测结果 AAAAAAAAAA
题目名称 QAQ的最短路 最终得分 100
用户昵称 GravatarkZime 是否通过 通过
代码语言 C++ 运行时间 0.051 s
提交时间 2017-03-09 20:15:29 内存使用 0.48 MiB
显示代码纯文本
// kZime
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int MX = 103;
const double INF = 1e20;
double f[MX][MX], a[MX][MX];
int n, m;

inline int read() {
	int k = 0;
	char c = getchar();
	for(;!isdigit(c); c = getchar());
	for(; isdigit(c); c = getchar())k = k * 10 + c - '0';
	return k;
}


int main() {
#ifndef LOCAL
	freopen("boboji.in", "r", stdin);
	freopen("boboji.out", "w", stdout);
#endif

	n = read();
	m = read();
	
	for(int i = 1; i <= n; i++) {
		for(int j = 1; j <= n; j++) {
			if(i != j) {
				f[i][j] = f[j][i] = INF;
			}
		}
	}
	
	for(int i = 1; i <= m; i++) {
		int x = read();
		int y = read();
		int z = read();
		f[x][y] = f[y][x] = z;
		a[x][y] = a[y][x] = 1;
	}
	
	
	
	for(int k = 1; k <= n; k++) {
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(i != j && i != k && j != k){
					if(f[i][j] == f[i][k] + f[k][j]) {
						a[i][j] += a[i][k] * a[k][j]; 
					}else if(f[i][j] > f[i][k] + f[k][j]) {
						f[i][j] = f[i][k] + f[k][j];
						a[i][j] = a[i][k] * a[k][j];
					}
				}
				
			}
		}
	}
	
//	for(int i = 1; i <= n; i++) {
//		for(int j = 1; j <= n; j++) {
//			printf("%.3lf ",a[i][j]);
//		}
//		printf("\n");
//	}
	
	for(int k = 1; k <= n; k++) {
		double  Iv = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				if(f[i][j] == f[i][k] + f[k][j] && i != j && i != k && j != k && a[i][j] > 0){
					Iv += a[i][k] * a[k][j] / a[i][j];
				}
			}
		}
		printf("%.3lf\n",Iv);
	}
	 
	return 0;
}