P2164 [SHOI2007] Transportation Network

The renowned urban transit planner L.Serenade designed a subway network connecting the castles of OItown. Each subway line bidirectionally connects two castles. Since they are built underground at different depths, these lines can “cross.” The residents of OItown live and work in different castles, so every morning each resident departs from home and takes the subway to work. Transfers are allowed. However, each resident chooses a way to travel that minimizes the number of transfers. If there are multiple ways whose numbers of transfers are the same, then each resident chooses one of them uniformly at random every day. Now L.Serenade asks you to compute the expected passenger flow on each subway line every morning. He will tell you each resident’s home and workplace, as well as all information about the subway network he designed.

The first line contains two positive integers $n, m\ (2 \le n \le 300,\ n - 1 \le m \le \dfrac{n(n - 1)}{2})$, denoting the numbers of castles and lines. The next $m$ lines each contain two positive integers $u, v\ (1 \le u, v \le n,\ u \ne v)$, indicating a bidirectional line $u \leftrightarrow v$. Then follows an $n \times n$ matrix $\{C_{i,j}\}\ (0 \le C_{i,j} \le 100,\ C_{i,i} = 0)$, where $C_{i,j}$ denotes the number of residents who travel from $i$ to $j$ every morning. It is guaranteed that the transit network is connected, and for any two castles the number of optimal ways to travel (i.e., minimizing the number of transfers) does not exceed $2^{63} - 1$.

Output $m$ lines, each containing a number with one decimal digit, denoting the expected passenger flow on that line. The absolute error must not exceed $0.1$.

Sample explanation: The only resident will choose uniformly at random one of the following three paths: - $1 \to 2 \to 4 \to 6$. - $1 \to 2 \to 5 \to 6$. - $1 \to 3 \to 5 \to 6$. Translated by ChatGPT 5