题目：小明目前在做一份毕业旅行的规划。打算从北京出发，分别去若干个城市，然后再回到北京，每个城市之间均乘坐高铁，且每个城市只去一次。由于经费有限，希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱，找到每个城市只访问一次并返回起点的最小车费花销。
题目解析：找一条从起点出发，遍历所有城市且只遍历一遍，最后返回起点，最小花销是多少？可以看出这是就是求所有城市的遍历顺序，花费最小的遍历顺序就是所求，既是求遍历顺序，可以用状态压缩，一共有O(1<<N)种状态，为了转移到下一个状态，需要知道每种状态下的最后一个遍历城市是什么，所以再加一维状态（状态s下的最后一个遍历城市）， dp[s][i]为已经遍历完s中为1的位对应的城市，最后一个遍历城市为i的最少开销；
最初思路：遍历所有城市，以其为起点；然后用状态压缩+bfs，用inque存储每个(s,i)是否在queue中，空间复杂度为（3 * (1<<n)*20)，时间复杂度为O(n^3 * 2 ^ n)，既会TLE,也会MLE。。。。
优化：思路优化真的难，很难去突破现有的思路。。。这就导致想得出来就想，想不出来就gg了。。。。有一个重要的特征就是不管从哪个城市出发，最短路径都是一样的。证明：已知从城市i出发，最后回到城市i的最短路径为s，有一条更短的遍历路径为从城市j出发回到j，那么该路径也可以是从i出发最后回到i，也就是说从i出发，最后回到i还有一条更短的路径，与先前假设矛盾。（ps：这种有环的题我有点捉急。。。）
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n;
cin >> n;
vector<vector<int>> prices(n, vector<int>(n, 0));
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> prices[i][j];
int res = INT_MAX;
vector<vector<int>> stat(1 << n, vector<int>(n, INT_MAX));
stat[1][0] = 0;
for (int s = 1; s < (1 << n); s++)
{
for (int i = 0; i < n; i++)
{
if ((s & (1 << i)) == 0 || stat[s][i] == INT_MAX) continue;
for (int j = 1; j < n; j++)
{
if (s & (1 << j)) continue;
int ns = s | (1 << j);
stat[ns][j] = min(stat[ns][j], stat[s][i] + prices[i][j]);
}
}
}
for (int lc = 1; lc < n; lc++)
{
res = min(res, stat[(1 << n) - 1][lc] + prices[lc][0]);
}
cout << res << endl;
return 0;
}
原文链接: https://www.cnblogs.com/mychen06/p/12605879.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/339089
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
