2154: 宝典2第十一章清扫计划

【问题描述】清扫计划（cls.cpp/c/pas）POJ 3311

修罗王的猛兽军团虽然溃败了，但仍有不少猛兽逃窜到了魔法世界的各大城市（城市数不超过10个），给城市的安全带来极大的隐患，魔法学院为此派出一支特别小分队到各大城市清扫残余的猛兽，现已知到达各大城市所花费的时间，问到达所有城市清扫（清扫的时间可以忽略）并返回魔法学院的最少时间是多少？

【输入格式】

包括多组数据，每组数据第一行为城市N(1≤N≤10)，随后的N+1行，每行有N+1个数，表示魔法学院（以0表示）到N个城市（以1到10表示）的花费时间。第i行的第j个的值，表示直接从城市i到城市j的代价。需要注意的是，直接从城市i到城市j并不一定是最快的，这可能因为限速（比如高速路上突然限速40），比如红绿灯等等，另外，从城市i到城市j和从城市j到城市i的花费时间也不一定相同，所有数据以0结束。

【输出格式】

输出从魔法学院出发到达所有城市并返回所用的最少时间。

【输入样例】

3

0 1 10 10

1 0 1 2

10 1 0 10

10 2 10 0

0

【输出样例】

8