#290. #2352. 「NOI2007」 社交网络
-
ID: 290
传统题
1000ms
256MiB
尝试: 0
已通过: 0
难度: (无)
上传者:
#2352. 「NOI2007」 社交网络
说明
在社交网络 ( Social Network ) 的研究中，我们常常使用图论概念去解释一些社会现象。不妨看这样的一个问题:
在一个社交圈子里有 nnn 个人，人与人之间有不同程度的关系。我们将这个关系网络对应到一个 nnn 个结点的无向图上，两个不同的人若互相认识，则在他们对应的结点之间连接一条无向边，并附上一个正数权值 ccc ，ccc 越小，表示两个人之间的关系越密切。我们可以用对应结点之间的最短路长度来衡量两个人 sss 和 ttt 之间的关系密切程度，注意到最短路径上的其他结点为 sss 和 ttt 的联系提供了某种便利，即这些结点对于 sss 和 ttt 之间的联系有一定的重要程度。我们可以通过统计经过一个结点 vvv 的最短路径的数目来衡量该结点在社交网络中的重要程度。考虑到两个结点 AAA 和 BBB 之间可能会有多条最短路径。我们修改重要程度的定义如下：令 Cs,tC_{s,t}Cs,t 表示从s到t的不同的最短路的数目，Cs,t(v)C_{s,t}(v)Cs,t(v) 表示经过 vvv 从 sss 到 ttt 的最短路的数目；则定义：
为结点 vvv 在社交网络中的重要程度。为了使 I(v)I(v)I(v) 和 Cs,t(v)C_{s,t}(v)Cs,t(v) 有意义，我们规定需要处理的社交网络都是连通的无向图，即任意两个结点之间都有一条有限长度的最短路径。现在给出这样一幅描述社交网络的加权无向图，请你求出每一个结点的重要程度。
输入格式
输入第一行有两个整数 nnn 和 mmm ，表示社交网络中结点和无向边的数目。
在无向图中，我们将所有结点从 111 到 nnn 进行编号。接下来 mmm 行，每行用三个整数 a,b,ca , b , ca,b,c 描述一条连接结点 aaa 和 bbb ，权值为 ccc 的无向边。
注意任意两个结点之间最多有一条无向边相连，无向图中也不会出现自环（即不存在一条无向边的两个端点是相同的结点）。
输出格式
输出包括 nnn 行，每行一个实数，精确到小数点后 333 位。第 iii 行的实数表示结点 iii 在社交网络中的重要程度。
样例
样例输入
4 4
1 2 1
2 3 1
3 4 1
4 1 1样例输出
1.000
1.000
1.000
1.000样例解释
社交网络如下图所示。
对于 111 号结点而言，只有 222 号到 444 号结点和 444 号到 222 号结点的最短路经过 111 号结点，而 222 号结点和 444 号结点之间的最短路又有 222 条。因而根据定义，111 号结点的重要程度计算为 12+12=1\frac{1}{2} + \frac{1}{2} = 121+21=1 。由于图的对称性，其他三个结点的重要程度也都是 111 。
数据范围与提示
对于 50%50\%50% 的数据， n≤10,m≤45n \le 10 , m \le 45n≤10,m≤45。
对于 100%100\%100% 的数据， n≤100,m≤4500n \le 100 , m \le 4500n≤100,m≤4500 ，任意一条边的权值 ccc 是正整数且 1⩽c⩽10001 \leqslant c \leqslant 10001⩽c⩽1000 。
所有数据中保证给出的无向图连通，且任意两个结点之间的最短路径数目不超过 101010^{10}1010。