钢哥算法——第十一期
民间流行着有关三国时期的许多故事，其中最有名的就数千里走单骑。关羽保护着两位嫂嫂，从许都出发，过五关，斩六将，终于与刘备、张飞重聚于古城。
现在，你的任务是替关羽寻找一条新的路线，以找到他那比兔子跑得还快的哥哥。假定关羽知道从许都到古城各关卡间的所有道路、以及每个关卡平安通过的概率。请帮助关羽找到一条具有最大概率的有效路线。注意每个关卡他最多只能经过一次。
输入：
第一行有一个整数T (1 <= T <= 10)，表示测试情况的个数。
对于每种情况，第一行只有一个整数，N (3 <= N <= 1000)。接下来的N行是一个矩阵，表示从许都到古城的N–2个关卡之间的道路。如果第i行第j列处是1，则从i到j有一条道路；而0表示从i到j没有道路。每种情况的最后一行包含N–2个实数，其间以一个空格分开，分别表示关羽平安通过各关卡的概率P (0 <= P <= 1)。输入文件是jiuge2.in。
输出：（采用标准输出的形式。）
由许都出发平安到达古城的最大概率，要求精确到四位小数。如果结果小于0.0001，则输出“Cannot reach!”。
输入示例：
2
4
0 1 0 0
0 0 1 0
0 0 0 1
0 0 0 0
0.01 0.001
5
0 1 0 1 0
0 0 1 0 0
0 0 0 1 1
0 0 0 0 1
0 0 0 0 0
0.5 0.6 0.1
输入示例：
Case 1: Cannot reach!
Case 2: 0.3000
| 
