题目描述

题目描述略

输入格式

输入第一行有两个整数 n 和 m，表示社交网络中结点和无向边的数目。 在无向图中，我们将所有结点从 1 到 n 进行编号。 接下来 m 行，每行用三个整数 a,b,c 描述一条连接结点 a 和 b，权值为 c 的无向边。 注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。

输出格式

输出包括 n 行，每行一个实数，精确到小数点后 3 位。第 i 行的实数表示结点 i 在社交网络中的重要程度。

样例

输入样例 1

4 4
1 2 1
2 3 1
3 4 1
4 1 1

输出样例 1

1.000
1.000
1.000
1.000

输入样例 2

3 2
1 2 1
2 3 1

输出样例 2

0.000
2.000
0.000

输入样例 3

3 3
1 2 1
2 3 1
1 3 2

输出样例 3

0.000
1.000
0.000

提示

数据规模：n≤100,m≤4500，任意一条边的权值 c 是正整数且 1<=c<=1000。 所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过 10^10。

思路：1、在 Floyd 算法求最短路时同时更新路径条数。 2、用公式计算 Cs,t 是从s到t的最短路条数。 Cs,t(v) 是所有s到t的最短路中，经过v的条数。Cs,t(v)= S-V的路径条数*V-T的路径条数。