#2590. 旅行商变形 1

旅行商变形 1

Description

披萨店以尽可能快地向顾客提供披萨而自豪。司机将等待一个或多个(最多1010个)订单被处理,然后开始送货。他愿意走最短的路线运送这些货物,然后返回比萨店,即使这意味着途中要经过相同的地点或披萨店不止一次。

Format

Input

输入包含多个测试用例。每个测试用例的第1行都包含一个整数n1n10n(1≤n≤10),表示要交付的订单数量。之后n+1n+1行中的每一行都包含n+1n+1个整数,表示披萨店(编号00)和nn个位置(编号为1n1~n)之间的行程时间。第i行上的第j个值表示从位置i直接到位置jj的时间,时间值可能不对称,即从位置i直接到位置jj的时间可能与从位置j直接到位置i的时间不同。n=0n=0时将终止输入。

Output

对每个测试用例,都单行输出交付所有披萨并返回披萨店的最短时间。

Samples

3
0 1 10 20
1 0 1 2
10 1 0 10
10 2 10 0
0
8

来源

POJ3311