A17146. 红色站点最短运输路线
填空题
中等
知识点
题目描述
红色站点最短运输路线
题目描述
4 个站点（1~4），输入 4×4 距离矩阵。从 1 出发，遍历 2、3、4 后返回 1，求最短总距离。
输入格式
4 行，每行 4 个整数。
输出格式
一个整数。
参考答案
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int dist[5][5];
int main() {
for (int i = 1; i > dist[i][j];
}
}
int path[] = {2, 3, 4};
int min_len = INT_MAX;
do {
int len = dist[1][path[0]] + dist[path[0]][path[1]] +
dist[path[1]][path[2]] + dist[path[2]][1];
if (len < min_len) min_len = len;
} while (next_permutation(path, path + 3));
cout << min_len << endl;
return 0;
}答案解析
读取4×4整数矩阵，表示站点间距离。起点为1，需访问2、3、4各一次后返回1。枚举2、3、4的所有排列组合，每种顺序对应一条路径。对每条路径，按站点顺序累加相邻站点间距离，包括末站点回1的距离。计算所有路径的总距离，保留最小值。输出该最小值。
上一题
下一题