Description

Original statement (image):

To support various QoS requirements, modern networks consider parameters such as path delay, bandwidth, delay jitter, and loss rate when selecting routes. In a certain high-quality data transmission project, only two parameters are considered: network delay and loss rate.

The network can be represented by a simple undirected graph $G = (V, E)$, where $V$ is the set of nodes in the network and $E$ is the set of links (edges) between pairs of nodes. According to the project requirements, each edge has two parameters: latency and loss rate.

• The latency $t$ on an edge is the time required for data to travel from one endpoint to the other. It is an integer measured in milliseconds, with $0 \le t \le 100$.
• The loss rate $p$ of an edge is the percentage of data lost after transmission from one endpoint to the other, with $0 \le p \le 0.1$.

Route selection on network $G$ is defined as follows: given two nodes $u$ and $v$ in $G$, find a path between them.

For a path $P = v_1, v_2, v_3, \dots, v_n$ in $G$, suppose the latencies and loss rates of the edges on the path are

$$t_1, t_2, t_3, \dots, t_{n-1}, \quad p_1, p_2, p_3, \dots, p_{n-1}.$$

Then the total latency from $v_1$ to $v_n$ is

$$\sum_{i=1}^{n-1} t_i,$$

and the total loss rate is

$$1 - \prod_{i=1}^{n-1} (1 - p_i).$$

High-quality data transmission requirement: if data is to be transmitted from a node $u$ to another node $v$, then among all paths from $u$ to $v$, the chosen path must have the minimal loss rate; subject to this, the latency must be minimal.

Given two nodes in the network graph, find a path that satisfies the high-quality data transmission requirement.

Input Format

There are $2n+1$ lines.

• Line $1$: the number of nodes $n$ ($1 \le n \le 200$) and the indices of the two nodes $i, j$ to transmit data between ($1 \le i, j \le n$, $i \ne j$).

• Lines $2$ to $n+1$: the adjacency matrix of latencies $t$. Each element $t_{u,v}$ ($-1 \le t_{u,v} \le 100$, $t_{u,v} = t_{v,u}$, $t_{u,u} = 0$) gives the latency of the edge from node $u$ to node $v$. A value of $-1$ indicates that there is no edge between $u$ and $v$.

• Lines $n+2$ to $2n+1$: the adjacency matrix of loss rates $p$. Each element $p_{u,v}$ gives the loss rate of the edge from node $u$ to node $v$ (up to $4$ decimal places). A value of $-1$ indicates that there is no edge between $u$ and $v$.

It is guaranteed that $t_{u,v} = -1$ if and only if $p_{u,v} = -1$.

It is guaranteed that $p_{u,v} \in \{-1\} \cup [0, 0.1]$, $p_{u,v} = p_{v,u}$, and $p_{u,u} = 0$.

Output Format

Output $1$ line containing the latency and the loss rate of the chosen path. The latency is an integer and should be printed directly; the loss rate is a real number printed to $4$ decimal places.

3 1 3                       
0 1 5
1 0 2
5 2 0
0 0.1 0.05
0.1 0 0.05
0.05 0.05 0

5 0.0500

Hint

Translated by ChatGPT 5