河北省住房和城乡建设厅网站首页,网站蜘蛛屏蔽怎样恢复,网站导航栏目设计内容依据,番禺品牌型网站文章目录1. 题目2. 解题1. 题目
描述 有n个城市#xff0c;给出邻接矩阵arr代表任意两个城市的距离。 arr[i][j]代表从城市i到城市j的距离。Alice在周末制定了一个游玩计划#xff0c;她从所在的0号城市开始#xff0c;游玩其他的1 ~ n-1个城市#xff0c;最后回到0号。 A…
文章目录1. 题目2. 解题1. 题目
描述 有n个城市给出邻接矩阵arr代表任意两个城市的距离。 arr[i][j]代表从城市i到城市j的距离。Alice在周末制定了一个游玩计划她从所在的0号城市开始游玩其他的1 ~ n-1个城市最后回到0号。 Alice想知道她能完成游玩计划需要行走的最小距离。返回这个最小距离。除了城市0之外每个城市只能经过一次。
n10
arr[i][j]10000示例
例1:
输入:[[0,1,2],[1,0,2],[2,1,0]]
输出:4
解释:
[[0,1,2],[1,0,2],[2,1,0]]
有两种可能的方案。
第一种城市0-城市1-城市2-城市0cost5。
第二种城市0-城市2-城市1-城市0cost4。
返回4例2:
输入:[[0,10000,2],[5,0,10000],[10000,4,0]]
输出:11来源https://tianchi.aliyun.com/oj/141754208384739500/160296091929219253
2. 解题
n 比较小暴力回溯
class Solution {int ans INT_MAX;
public:/*** param arr: the distance between any two cities* return: the minimum distance Alice needs to walk to complete the travel plan*/int travelPlan(vectorvectorint arr) {// Write your code here.int n arr.size();if(n 0) return 0;vectorbool vis(n, false);vis[0] true;dfs(arr, vis, 0, 0, 0);return ans;}void dfs(vectorvectorint arr, vectorbool vis, int start, int ct, int dis){if(ct arr.size()-1)//走过的城市够个数了{if(dis arr[start][0] ans)ans arr[start][0] dis;return;}for(int i 1; i arr.size(); i){ // 1 - n-1 城市if(vis[i])//走过了跳过continue;vis[i] true;dfs(arr, vis, i, ct1, disarr[start][i]);vis[i] false;}}
};754ms C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
