字节研发:毕业旅行"/>
牛客网:19字节研发:毕业旅行
众所周知这是一个旅行商问题,是个NPhard的问题,城市小于等于20个,费用小于1000,也就是说最高费用在2k左右。
这里用动态规划解答,有一篇博客分析的很好:
C++笔试编程题4:毕业旅行及旅行商问题总结_孤帆扁舟去的博客-CSDN博客_旅行商问题心得体会
我们要设置函数和转移方程。
这里设置dp[i][j],其中i表示状态,例如有n个城市,则i的取值是0-2^n-1表示可能的已经经过的城市。j表示经过这些城市最后到达的终点。
也就是状态dp。
这里我们利用已知的信息推导出未知,首先dp[1][0]=0,含义是经过了第一个城市,终点是第一个城市。
具体的状态转移方程如下所示:
dp[i | 1<<k][j] = min(dp[i][j]+nums[j][k],dp[1 | 1<<k][j])
注意的是这里的dp[i][j]一定是已经更新过的信息,由于初始化的时候全部初始化为最大代价,所以我们一开始是拿dp[1][0]去更新其他路径的,
具体代码如下所示:
#include <bits/stdc++.h>
using namespace std;
const int MAX = 50000;int getAns(vector<vector<int>> &nums){int n=nums.size();int stateNum=1<<n;vector<vector<int>> dp(stateNum,vector<int>(n,MAX));dp[1][0]=0;for (int i = 0; i < stateNum; ++i) {// 对所有状态而言for (int j = 0; j < n; ++j) {// 对所有状态 以j结尾的dp而言if (dp[i][j]!=MAX){// 不为MAX说明是更新过的 则可利用其更新其他的路径for (int k = 0; k < n; ++k) {if ((i&(1<<k))==0){dp[i | (1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+nums[j][k]);}}}}}int res=MAX;for (int i = 1; i < n; ++i) {res= min(res,dp[stateNum-1][i]+nums[i][0]);}return res;
}int main() {int n;while(cin>>n){vector<vector<int>> edges(n,vector<int>(n,0));for (int i = 0; i < n; ++i) {for (int j = 0; j < n; ++j) {cin>>edges[i][j];}}cout<<getAns(edges)<<endl;}return 0;
}
这里的做法还保证了出发点一定是北京
更多推荐
牛客网:19字节研发:毕业旅行
发布评论