19-大数据一班-杨文冠的博客

Travelling 来自专栏

题意：n 个城市已及 m 条路以及对应路费 c，要求遍历所有城市最少的路费，每个城市不能超过2次。思路：三进制位表示一个城市被走过的次数，三进制没有位运算，可以预处理三进制位每一位的权值以及每个十进制数的三进制表示。状态方程：表示访问中所有的点后最后到达城市（感觉紫书上对旅行商的解析不太好）转移...

旅行商问题来自专栏

问题描述：给定一个给顶点组成的带权有向图的距离矩阵。要求从顶点出发，经过每个顶点恰好一次后在回到顶点.问所经过的边的总权重的最小值是多少？所有可能的路线共有种，尽管很小了，仍然无法枚举每一种情况。用跑遍求解不能保证求出的最小值经过了所有的城市。方法一：记忆化搜索，表示从出发访问剩余所有顶点...

最短路练习

hdu 2433 好像是Dijkstra算法的变形，最短路生成树。题意：我老是看不懂题目说什么，N个城镇，M条边，每条边的距离都是1（当然两个城镇之间可能有多条边，也可能没有边），求城镇i到城镇j的最短路之和，即∑i=1n(∑j=1ndis[j])\sum_{i=1}^{n}{ (\sum_{j...

Travelling 来自专栏

旅行商问题 来自专栏

最短路练习

旅行商问题来自专栏