P2269 [HNOI2002] High-Quality Data Transmission

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.

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 $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.

Translated by ChatGPT 5