题目描述

$%原题面是：$

目前的网络为了支持各种 QoS 需求，在进行路由选择时所考虑的路由参数主要有网络路径中的参数如时延、网络带宽、时延抖动及丢失率等参数，在某种高质量的数据传输工程中仅考虑网络的时延和丢失率两个参数。

网络可以用一个简单无向图 $G = (V, E)$ 来表示，$V$ 是网络中结点的集合，$E$ 是两个结点之间的链路，即边。依据工程的要求，每条边上有两个参数：时延和丢失率。

• 边上的时延 $t$ 是数据从该边的一个端点传输到另一个端点所需要的时间，取为整数，单位是毫秒，$0 \le t \le 100$。
• 一条边的丢失率 $p$ 是数据从该边的一个端点传输到另一个端点后丢失数据的百分比，$0 \le p \le 0.1$。

所谓网络 $G$ 上的路由选择是：给定 $G$ 中的两个结点 $u$ 和 $v$，找出这两个结点之间的一条路径。

---

对于网络 $G$ 的一条路径 $P = v_1, v_2, v_3, \dots, v_n$，假设该路径上各边的时延和丢失率分别是：

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

则数据从 $v_1$ 传输到 $v_n$ 的时延是：

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

丢失率是：

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

---

本题的高质量数据传输要求：如果数据要从一个结点 $u$ 传输到另一个结点 $v$，则所传输路径的丢失率是从 $u$ 到 $v$ 的所有路径中最小的，而且在该前提下时延最小。

请为网络图给定的两个结点，找出满足高质量数据传输要求的路径。

输入格式

共有 $2n+1$ 行。

第 $1$ 行是网络的节点数 $n\ (1 \le n \le 200)$ 和数据要传输的两个结点的序号 $i,j\ (1 \le i,j \le n, i \ne j)$。

第 $2$ 行到第 $n+1$ 行是时延 $t$ 的邻接矩阵，其元素 $t_{u,v}\ (-1 \le t_{u,v} \le 100,t_{i,j}=t_{j,i},t_{i,i}=0)$ 的值是第 $u$ 个结点到第 $v$ 个结点的边的时延，当其值为 $-1$ 时表示第 $u$ 个结点到第 $v$ 个结点无边。

第 $n+2$ 行到第 $2n+1$ 行是丢失率 $p$ 的邻接矩阵，其元素 $p_{u,v}$ 的值是第 $u$ 个结点到第 $v$ 个结点的边的丢失率（最多精确到小数点后 $4$ 位），当其值为 $-1$ 时表示第 $u$ 个结点到第 $v$ 个结点无边。

保证 $t_{u,v}=-1$ 当且仅当 $p_{u,v}=-1$。

保证 $p_{u,v} \in \{-1\} \cup [0,0.1],p_{u,v}=p_{u,v},p_{u,u}=0$。

输出格式

共 $1$ 行，输出所找出的路径的时延和丢失率。（时延是整数，直接输出即可；丢失率是实数，精确到小数点后 $4$ 位）

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