首页 > 其他 > 详细

字节19年春招笔试-毕业旅行

时间:2020-03-31 16:19:20      阅读:166      评论:0      收藏:0      [点我收藏+]

题目:小明目前在做一份毕业旅行的规划。打算从北京出发,分别去若干个城市,然后再回到北京,每个城市之间均乘坐高铁,且每个城市只去一次。由于经费有限,希望能够通过合理的路线安排尽可能的省一些路上的花销。给定一组城市和每对城市之间的火车票的价钱,找到每个城市只访问一次并返回起点的最小车费花销。

题目解析:找一条从起点出发,遍历所有城市且只遍历一遍,最后返回起点,最小花销是多少?可以看出这是就是求所有城市的遍历顺序,花费最小的遍历顺序就是所求,既是求遍历顺序,可以用状态压缩,一共有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;
}

  

字节19年春招笔试-毕业旅行

原文:https://www.cnblogs.com/mychen06/p/12605879.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!