A17089. 蒙古族游牧路线规划
填空题
中等
知识点
题目描述
蒙古族游牧路线规划
题目描述
蒙古族游牧民逐水草而居，需在n个牧场间规划迁徙路线。牧场编号1~n，已知任意两个牧场间的距离，牧民从1号牧场出发，遍历所有牧场后返回起点，要求总路程最短，还原游牧生活的智慧。请计算最短迁徙总路程。
输入格式
第一行输入整数n（3≤n≤7）；接下来n行，每行n个整数，为牧场间距离矩阵（距离≤100，自身距离为0）。
输出格式
输出一个整数，表示最短迁徙总路程。
参考答案
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int main() {
int n;
cin >> n;
vector<vector<int>> dist(n, vector<int>(n));
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin >> dist[i][j];
vector<int> path(n-1);
for(int i=0; i<n-1; i++) path[i] = i+1;
int min_sum = INT_MAX;
do{
int sum = dist[0][path[0]];
for(int i=0; i<n-2; i++) sum += dist[path[i]][path[i+1]];
sum += dist[path.back()][0];
if(sum < min_sum) min_sum = sum;
}while(next_permutation(path.begin(), path.end()));
cout << min_sum << endl;
return 0;
}答案解析
1. 读取牧场数量n和n×n的距离矩阵，存储为二维数组。
2. 由于n范围为3到7，可采用全排列枚举所有可能的访问顺序。
3. 固定起点为1号牧场，对剩余2到n号牧场生成所有排列。
4. 对每种排列计算总路程：从1号出发，按排列顺序访问每个牧场，最后返回1号。
5. 路程累加依据距离矩阵中对应牧场间的预存值。
6. 在所有排列对应的总路程中维护最小值。
7. 输出该最小值作为最短迁徙总路程。 知识点 使用枚举法解决较为简单的问题、STL中string, vector, set, map的使用方法、编写完成指定功能的正确完整的程序、基本的输入输出方法、数组的遍历、循环结构、多层循环结构、函数的调用方法、使用枚举法解决较为简单的问题、STL中string, vector, set, map的使用方法、编写完成指定功能的正确完整的程序、基本的输入输出方法、循环结构嵌套、数组的遍历、变量的定义、函数的调用方法
上一题
下一题