TSP问题
问题 tsp
2023-09-11 14:14:59 时间
Hie with the Pie
题目传送:POJ - 3311 - Hie with the Pie
AC代码:
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cctype>
#include <cstdio>
#include <string>
#include <vector>
#include <complex>
#include <cstdlib>
#include <cstring>
#include <fstream>
#include <sstream>
#include <utility>
#include <iostream>
#include <algorithm>
#include <functional>
#define LL long long
#define INF 0x7fffffff
using namespace std;
int n;
int mp[15][15];
int dp[1300][13];//dp[state][i]表示到达i点状态为state的最短距离
void floyd() {
for(int k = 0; k <= n; k ++) {
for(int i = 0; i <= n; i ++) {
for(int j = 0; j <= n; j ++) {
if(mp[i][j] > mp[i][k] + mp[k][j]) {
mp[i][j] = mp[i][k] + mp[k][j];
}
}
}
}
}
int main() {
while(scanf("%d", &n) != EOF) {
if(n == 0) break;
for(int i = 0; i <= n; i ++) {
for(int j = 0; j <= n; j ++) {
scanf("%d", &mp[i][j]);
}
}
floyd();
memset(dp, 0x3f, sizeof(dp));
for(int state = 0; state < (1 << n); state ++) {//枚举全部状态
for(int i = 1; i <= n; i ++) {
if(state & (1 << (i - 1))) {//状态中已经经过了城市i
if(state == (1 << (i - 1))) {//状态中仅仅经过城市i
dp[state][i] = mp[0][i];
}
else {//状态中除了经过了城市i还经过了其它城市
for(int j = 1; j <= n; j ++) {
if(i != j && state & (1 << (j - 1))) {
dp[state][i] = min(dp[state][i], dp[state ^ (1 << (i - 1))][j] + mp[j][i]);
}
}
}
}
}
}
int ans = INF;
for(int i = 1; i <= n; i ++) {
ans = min(ans, dp[(1 << n) - 1][i] + mp[i][0]);
}
printf("%d\n", ans);
}
return 0;
}
相关文章
- oauth2 问题 Full authentication is required to access this resource 探索
- 项目中遇到的问题:关系图组件兼容性问题解决
- Java实现蓝桥杯正则问题
- MYSQL随机抽取查询 MySQL Order By Rand()效率问题
- C#进阶系列——WebApi 跨域问题解决方案:CORS
- 关于layer.photos图片点击无法弹出的问题分析。
- C# POST XML(修正中文乱码问题)
- MAT之GA:遗传算法(GA)解决M-TSP多旅行商问题
- 改进遗传算法在TSP问题中的应用(Matlab代码实现)
- 【路径优化】基于帝企鹅算法求解TSP问题(Matlab代码实现)
- 结合邻域连接法的蚁群优化(NACO)求解TSP问题(Matlab代码实现)
- 基于象鼻虫损害优化算法的TSP问题求解(Matlab代码实现)
- 基于A*、RBFS 和爬山算法求解 TSP问题(Matlab代码实现)
- 基于改进遗传算法求解 TSP/MTSP 【旅行推销员问题 (TSP)、多旅行推销员问题 (M-TSP) 】(Matlab代码实现)
- 【TSP问题】基于改进蜜蜂算法解决旅行商问题(Matlab代码实现)