阿里的30分钟编程测评，截图献上

Map = [[0,2,3],[2,0,1],[3,1,0]] ans = [([float('inf')]*3)for p in range(3)] start = 0 def findfunc(Node,N,distance):         if N == 0:             if ans[start][Node] > distance:                 ans[start][Node] = distance                 return             return         info = Map[Node]         for ind,each in enumerate(info):             if each != 0:                 findfunc(ind,N-1,distance + each)         return for i in range(3):     start = i     M = findfunc(i,2,0) 深度优先搜索

TSP是什么意思?

唉，我是时间过了才写出来的，也没用

我只做出来一个时间复杂度为n3*m的

用动态规划做的，dp[i][j][m]=min{dp[i][s][m-1] + map[s][j]}s为j的所有邻居。当然用二维滚那个动数组可以节约一点空间。但是时间复杂度为O(n^3*m)，不合要求。。。

之前图相关的都用的领接数组，这换成了领接矩阵，半天没反应过来，我去。。。。。 #include<iostream> #include<algorithm> #include<fstream> #include<map> #include<vector> #include<string> #include<iostream> using namespace std; void dfs(vector<vector<int>> &path, int s, int e, int v,int &res,int L,int M) {     if (L > M)         return;     if(L==M&&s==e){         res = min(res, v);         return;     }     for (int i = 0; i < path[0].size(); ++i) {         if (path[s][i] != 0)             dfs(path, i, e, v + path[s][i], res, L + 1, M);     } } vector<vector<int>> solve(vector<vector<int>> &path,int M) {     vector<vector<int>> res(path.size(), vector<int>(path[0].size(), -1));     for(int i=0;i<path.size();++i)         for (int j = 0; j < path[0].size(); ++j) {             int r=INT32_MAX;             dfs(path,i,j,0,r,0,M);             res[i][j] = r;         }     return res; } int main(void){     int N, M;     while (cin >> N >> M) {         int N1, N2;         cin >> N1 >> N2;         vector<vector<int>> path;         for (int i = 0; i < N1; ++i) {             vector<int> temp;             int data;             for (int j = 0; j < N2; ++j) {                 cin >> data;                 temp.push_back(data);             }             path.push_back(temp);         }         vector<vector<int>> res = solve(path, M);         for (auto v : res) {             for (auto i : v)                 cout << i << " ";             cout << endl;         }     }     getchar();     return 0; }