XTU 1186 Tourist 2

2023-12-15 17:59

文章标签 xtu tourist 1186

本文主要是介绍XTU 1186 Tourist 2，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Tourist 2
[ Submit Code ] [ Top 20 Runs ]
Acceteped : 37		Submit : 120
Time Limit : 1000 MS		Memory Limit : 65536 KB

Description
题目描述 Eric喜欢旅行，今年暑假终于可以有几天时间出去玩了。他计划在去N个不同的城市，而且不想重复去相同的城市，最后需要回到出发的城市，他想知道怎么走可以让差旅费用降到最低？我们把城市编号为0~N，Eric总从0号城市出发。输入第一行是一个整数K，表示样例的个数。每个样例的第一行为一个整数N(1≤N≤9)，表示想去N个城市。以后的N行，每行N个整数X_ij,第i行第j列个整数表示从城市i到城市j所需要的旅费，单次费用不超过1000。i = j 时，X_ij = 0。输出每行输出一个样例的结果，包括两行，第一行是差旅的总费用，第二行是3个城市的编号序列，每个城市编号之间用一个空格隔开，表示旅行的路线，如果存在多条线路都是最少花费，请按字典序输出这些线路，每个线路一行，最多输出10条线路。样例输入 1 3 0 1 1 1 2 0 2 2 3 3 0 3 4 4 4 0 样例输出 10 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1

Sample Input


Sample Output


Source


[ Submit Code ] [ Top 20 Runs ]

思路：是XTU1184的加强版。很容易想到，因为每个城市只能去一次，且数据最大为9，因此，也可以枚举所有解。这样，其实就可以转化为类似N皇后的问题了。故采用回溯法来解决，期间有一个优化过程，即在继续寻找之前，先判断是否比当前最优解更优，如果没有当前最优解优，就没必要继续找下去了。详见代码。

AC代码如下：

#include <bits/stdc++.h>
using namespace std;
const int maxn = 10;
int w[maxn][maxn], ans[maxn][maxn];
bool vis[maxn];
int way[maxn];
int n, mind, cnt;void dfs(int d, int k, int num){if (num == n){int t = d+w[k][0];if (t > mind)return ;if (t==mind && cnt<9){++cnt;for (int i=1; i<=n; ++i)ans[cnt][i] = way[i];}else if (t < mind){cnt = 0;mind = t;for (int i=1; i<=n; ++i)ans[cnt][i] = way[i];}return ;}for (int i=1; i<=n; ++i)if (!vis[i] && d+w[k][i]<mind){vis[i] = true;way[num+1] = i;dfs(d+w[k][i], i, num+1);vis[i] = false;}
}int main(){ios::sync_with_stdio(false);cin.tie(0);int T;scanf("%d", &T);while (T--){scanf("%d", &n);for (int i=0; i<=n; ++i)for (int j=0; j<=n; ++j)scanf("%d", &w[i][j]);mind = INT_MAX;dfs(0, 0, 0);printf("%d\n", mind);for (int i=0; i<=cnt; ++i){for (int j=1; j<n; ++j)printf("%d ", ans[i][j]);printf("%d\n", ans[i][n]);}}return 0;
}