National Olympiad in Informatics, China, 2007
In the study of social networks, we commonly use graph theory to explain
certain social phenomena.
Let's look at a problem regarding this. There are
people in a social
group. Between people, there are different levels of relationships. We
represent this relationship network using an undirected graph with
nodes. If two different people are familiar with each other, then there
will exist an undirected edge between their corresponding nodes on the
graph. Additionally, the edge will have a positive weight
– the
smaller the value of
, the closer the relationship between the two
people.
We can use the shortest path between the corresponding nodes of two
people
and
to measure the closeness of their relationship. Note
that other nodes on the shortest path provide some level of benefit to
the relationship between
and
, and that these nodes have a
certain level of importance with respect to
and
's relationship.
Through analysis of the shortest paths passing through node
, we can
measure
's importance level to the entire social network.
Observing that there may be multiple shortest paths between nodes
and
, we revise our definition of the importance level as follows:
Let
represent the number of shortest paths between nodes
and
, and
represent the number of shortest paths
between nodes
and
which passes through
. The importance
level of node
to the social network is defined as:

To ensure that
and
are always defined, we will
only deal with social networks that can be represented by connected,
undirected graphs. Furthermore, there will always exist a shortest path
of finite length between any pair of nodes.
Given such a weighted, undirected graph representing the social network,
please calculate the importance level of each node.
Input Specification
The first line of input contains two integers
and
, representing
the number of nodes and the number of undirected edges in the social
network. The nodes in the graph are numbered consecutively from
to
.
For the next
lines, each line contains three integers
,
, and
describing an undirected edge connecting nodes
and
with
weight
. Note that there will be at most one undirected edge between
any pair of nodes, and no loops will occur within the graph (where the
two ends of an edge rest on the same node).
Output Specification
Output
lines, each line containing a single real number, accurate to
digits after the decimal point. Line
represents the importance of
node
to the social network. Your outputted numbers will be
considered correct if the absolute differences between them and the
correct values do not exceed
.
Sample Input
Copy
4 4
1 2 1
2 3 1
3 4 1
4 1 1
Sample Output
Copy
1.000
1.000
1.000
1.000
Explanation
The social network is depicted in the following figure.
Regarding node
, only the shortest path from
to
and the shortest
path from
to
pass through it. There are
different shortest paths
between nodes
and
. According to the definition, the importance level
of node
is
. Due to the
symmetry of the graph, the other three edges also have importance levels
of
.
Constraints
For
of the test cases:
.
For
of the test cases:
, and the weight
of
any edge will be a positive integer satisfying
.
It is guaranteed that the data will consist of connected, undirected
graphs, and that the number of shortest paths between any two nodes will
not exceed
.
Problem translated to English by Alex.
Comments