问题2140--旅行商变形1（POJ3311）

2140: 旅行商变形1（POJ3311）

时间限制: 1 Sec  内存限制: 128 MB
提交: 1  解决: 1
[提交] [状态] [讨论版] [命题人:]

题目描述

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

输入

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

输出

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

样例输入 Copy 

3
0 1 10 10
1 0 1 2
10 1 0 10
10 2 10 0
0

样例输出 Copy 

8

来源/分类

动态规划算法 状压DP 
[提交] [状态]