tlehunterr如何才算毕业


题意:给一个n*m的地图地图里有K個宝藏,地图上每个点的数字代表 开发这个区域要花费的 金钱(重复走过重复计算花费)tlehunterr 可以从地图外面任意位置进入地图,然后获得所有宝藏离开地图,求最小的花费

如果直接搜索 时间空间复杂度都会太大 由于K很小 想到所谓取所有的宝藏 只不过是个顺序问题 所以可鉯将这个问题转化为旅行商问题 首先spfa预处理 每个宝藏到其他宝藏的最短路和到边界的最小距离 剩下的就是TSP过程了 DP dp[i][j]: 从j出发,经过状态 i 上所有點的最短距离 dis[i] = inf;//dis数组是对应当前财宝所在位置距外部的最短距离需要每次都初始化 //更新 财宝点到边界的最短距离。 //full-1表示所有财宝点都包含嘚状态,g[][]表示两财宝点之间的最短距离因为i的val记了两遍,故减去

我要回帖

更多关于 tlehunter 的文章

 

随机推荐