ccf#NOI2007A. 社交网络 (Social Network)
社交网络 (Social Network)
Description
There are individuals in a social network, and there are different relationships between people. We represent this relational network as an undirected graph with nodes. If two different people know each other, we connect an undirected edge between the corresponding nodes and assign a positive weight , the smaller the , the closer the relationship between the two people. We can use the shortest path length between the corresponding nodes to measure the closeness of the relationship between two people and . Note that other nodes on the shortest path have a certain degree of importance for the connection between and . We can measure the importance of the node in the social network by counting the number of shortest paths passing through a node . Note that there may be multiple shortest paths between two nodes and .
We modify the definition of importance as follows: Let represent the number of different shortest paths from to , represents the number of shortest paths from to passing through ; then it is defined as:
$$I(v) =\sum_{s \neq v, t \neq v}\frac{C_{s,t}(v)}{C_{s,t}} $$It is guaranteed there is a shortest path of finite length between any two nodes. Now given such a weighted undirected graph describing a social network, please find the importance of each node.
Input Format
There are two integers and in the first line of input, which represent the number of nodes and the number of undirected edges in the social network.
In the undirected graph, we number all nodes from to .
In the next lines, each line contains three integers to describe an undirected edge connecting nodes and with a weight of .
Note that there is at most one undirected edge connected between any two nodes, and there will be no self-loop in the undirected graph.
Output Format
The output consists of lines, one real number per line, accurate to digits after the decimal point. The real number in row indicates the importance of node in the social network.
4 4
1 2 1
2 3 1
3 4 1
4 1 1
1.000
1.000
1.000
1.000
Constraints
For data, .
For data, , the weight of any edge is a positive integer where .
It is guaranteed that the undirected graph is connected and the number of shortest paths between any two nodes doesn't exceed .