文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

描述
有n個城市，給出鄰接矩陣arr代表任意兩個城市的距離。
arr[i][j]代表從城市i到城市j的距離。Alice在周末制定了一個游玩計劃，她從所在的0號城市開始，游玩其他的1 ~ n-1個城市，最后回到0號。
Alice想知道她能完成游玩計劃需要行走的最小距離。返回這個最小距離。除了城市0之外每個城市只能經過一次。

n<=10 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->城市0，cost=5。 第二種，城市0->城市2->城市1->城市0，cost=4。 返回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(vector<vector<int>> &arr) {// Write your code here.int n = arr.size();if(n == 0) return 0;vector<bool> vis(n, false);vis[0] = true;dfs(arr, vis, 0, 0, 0);return ans;}void dfs(vector<vector<int>> &arr, vector<bool> &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, ct+1, dis+arr[start][i]);vis[i] = false;}} };

754ms C++

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的天池 在线编程 旅行计划（暴力回溯）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。