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个城市的编号序列，每个城市编号之间用一个空格隔开，表示旅行的路线，如果存在多条线路都是最少花费，请输出字典序输出这些线路，每个线路一行。 样例输入复制代码
样例输出复制代码
| ||
Sample Input | ||
复制代码
| ||
Sample Output | ||
复制代码
| ||
Source | ||
| [ Submit Code ] [ Top 20 Runs ] | ||
思路：每个城市只能去一次，只有3个城市，因此最多只有3！种情况。故将所有情况枚举一遍，求出最优解，最后再判断所有情况是否是最优解，是的话就输出，不是就忽略。详见代码。
AC代码如下：
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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("%dn", 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 %dn", i, j, k);
}
return 0;
}
最后
以上就是隐形羽毛最近收集整理的关于XTU 1184 Tourist 1的全部内容，更多相关XTU内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
![[GDUT]:1059: 二维数组排序](/uploads/reation/bcimg4.png)
发表评论 取消回复