Toggle navigation
NKZX_NOI_OJ
常见问答
题库
来源/分类
状态
排名
竞赛&作业
Login
问题2139--旅行商问题Ⅰ
2139: 旅行商问题Ⅰ
时间限制:
1 Sec
内存限制:
512 MB
提交:
2
解决:
2
[
提交
] [
状态
] [
讨论版
] [命题人:
]
题目描述
旅行商问题,即TSP问题(Travelling Salesman Problem)又译为旅行推销员问题、货郎担问题,是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路径的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值,并输出所选择的路径。
假设所拜访的n个城市构成一个有向图,且城市结点编号从0开始编号,确保存在能返回的路径,如下图所示,每个结点表示一个城市,每条边上的权表示两个城市之间的路径距离,求从0节点出发经过每个节点一次且只有一次回到0节点的最短路径值。
输入
第一行,两个正整数n和m,分别表示城市的数目和所构成的有向图的边数。
接下来m行,每行三个整数,分别表示每条有向边的起点 、终点和边上的权。
输出
一行
一个整数,表示最短路径线路的距离。
样例输入
Copy
5 8 0 1 3 0 3 4 1 2 5 2 0 4 2 3 5 3 4 3 4 0 7 4 1 6
样例输出
Copy
22
来源/分类
动态规划算法
状压DP