本文主要是介绍XTU 1184 Tourist 1，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Tourist 1 | ||
| [ Submit Code ] [ Top 20 Runs ] | ||
| Acceteped : 79 | Submit : 214 | |
| Time Limit : 1000 MS | Memory Limit : 65536 KB | |
Description | ||
题目描述Eric喜欢旅行，今年暑假终于可以有几天时间出去玩了。他计划在去3个不同的城市，而且不想重复去相同的城市，最后回到出发的城市，他想知道怎么走可以让差旅费用降到最低？ 我们把城市编号为0~3，Eric总从0号城市出发。 输入第一行是一个整数K，表示样例的个数。 每个样例占4行，每行4个整数Xij,第i行第j列个整数表示从城市i到城市j所需要的旅费，单次费用不超过1000。i = j 时，Xij = 0。 输出每行输出一个样例的结果，包括两行，第一行是差旅的总费用，第二行是3个城市的编号序列，每个城市编号之间用一个空格隔开，表示旅行的路线，如果存在多条线路都是最少花费，请输出字典序输出这些线路，每个线路一行。 样例输入1 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 ] | ||
思路：每个城市只能去一次，只有3个城市，因此最多只有3！种情况。故将所有情况枚举一遍，求出最优解，最后再判断所有情况是否是最优解，是的话就输出，不是就忽略。详见代码。
AC代码如下：
#include <bits/stdc++.h>
using namespace std;
int w[4][4], d[4][4][4];int main(){ios::sync_with_stdio(false);cin.tie(0);int T;scanf("%d", &T);while (T--){for (int i=0; i<4; ++i)for (int j=0; j<4; ++j)scanf("%d", &w[i][j]);int ans = INT_MAX;for (int i=1; i<4; ++i)for (int j=1; j<4; ++j)for (int k=1; k<4; ++k)if (i!=j && j!=k && i!=k){d[i][j][k] = w[0][i]+w[i][j]+w[j][k]+w[k][0];if (d[i][j][k] < ans)ans = d[i][j][k];}printf("%d\n", ans);for (int i=1; i<4; ++i)for (int j=1; j<4; ++j)for (int k=1; k<4; ++k)if (i!=j && j!=k && i!=k && d[i][j][k]==ans)printf("%d %d %d\n", i, j, k);}return 0;
}
这篇关于XTU 1184 Tourist 1的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
