OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1267--旅行商问题

1267: 旅行商问题

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

题目描述

旅行商问题是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。

--摘自百度百科      

输入

第一行一个正整数n表示城市数量。(n <= 13)
接下来输入一个n行n列邻接矩阵，第i行j列一个非负整数d表示城市i到j的距离。(d <= 1e7)
保证城市i到j的距离等于城市j到i的距离且到自身距离为0。

输出

输出一个非负整数表示经过每个城市一次且仅一次并回到起点的最短距离。

样例输入 Copy 

4
0  5  9  4
5  0  13 2
9  13 0  7
4  2  7  0

样例输出 Copy 

23

来源/分类

分支限界法 
[提交] [状态]