C++ 蛮力法解决商旅问题：高效算法实现及测试用例

以下是一个 C++ 蛮力法解决商旅问题的示例代码：

#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max();

int n, m;
vector<vector<int>> graph;

void readGraph(string filename) {
    ifstream fin(filename);
    fin >> n >> m;
    graph.resize(n, vector<int>(n, INF));
    for (int i = 0; i < m; i++) {
        int u, v, w;
        fin >> u >> v >> w;
        graph[u][v] = w;
        graph[v][u] = w;
    }
    fin.close();
}

void bruteForce() {
    vector<int> nodes(n);
    for (int i = 0; i < n; i++) {
        nodes[i] = i;
    }
    int minDist = INF;
    vector<int> minPath;
    do {
        int dist = 0;
        for (int i = 0; i < n - 1; i++) {
            dist += graph[nodes[i]][nodes[i + 1]];
        }
        if (dist < minDist) {
            minDist = dist;
            minPath = nodes;
        }
    } while (next_permutation(nodes.begin() + 1, nodes.end()));
    cout << 'Minimum distance: ' << minDist << endl;
    cout << 'Path: '; 
    for (int i = 0; i < n; i++) {
        cout << minPath[i] << ' ';
    }
    cout << endl;
}

int main() {
    readGraph('graph1.txt');
    bruteForce();
    readGraph('graph2.txt');
    bruteForce();
    readGraph('graph3.txt');
    bruteForce();
    return 0;
}

该代码首先定义了一个常量 INF 表示无穷大，然后定义了全局变量 n 和 m 表示图的顶点数和边数，以及一个二维 vector graph 表示图的邻接矩阵。readGraph 函数从文件中读取图的信息并初始化 graph。bruteForce 函数对所有可能的路径进行枚举，并输出最短路径的长度和路径上的节点信息。最后，main 函数分别读取 3 个测试用例的图并调用 bruteForce 函数进行求解。

需要注意的是，蛮力法的时间复杂度为 O(n!)，因此只适用于规模较小的图。对于规模较大的图，需要使用更高效的算法，如 Dijkstra 算法、Bellman-Ford 算法或 Floyd 算法。