317005 - 清扫计划

【题目描述】17.5 清扫计划(cls)POJ 3311 有不少猛兽逃窜到了各大城市(城市数不超过10个),给城市的安全带来极大的隐患,管理部门为此派出一支特别小分队到各大城市清扫残余的猛兽,现已知到达各大城市所花费的时间,问到达所有城市清扫(清扫的时间可以忽略)并返回管理部门的最少时间是多少?

输入

输入包括多组数据,每组数据第一行为城市数N(1≤N≤10),随后的N+1行,每行有N+1个数,表示管理部门(以0表示)到N个城市(以1到10表示)的花费时间。第i行的第j个的值,表示直接从城市i到城市j的代价。需要注意的是,直接从城市i到城市j并不一定是最快的,另外,从城市i到城市j和从城市j到城市i的花费时间也不一定相同,所有数据以0结束。

输出

输出从管理部门出发到达所有城市并返回管理部门所用的最少时间。

样例

输入

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

输出

8
时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题