邮递员问题c++

邮递员问题是一个著名的旅行商问题。该问题的目标是找到一条路线，使得一个邮递员可以在一个城市中经过所有的街道，然后返回起点，而且路线的总长度最短。

C++代码如下：

#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

const int N = 5;
const int INF = 1000000; // 表示两点之间没有连通

int graph[N][N] = {
    {0, 2, 6, 5, INF},
    {2, 0, INF, 7, 1},
    {6, INF, 0, INF, 3},
    {5, 7, INF, 0, INF},
    {INF, 1, 3, INF, 0},
}; // 城市地图

void print(int *path) { // 打印路径
    for (int i = 0; i < N; ++i) {
        cout << path[i] << " ";
    }
    cout << path[0] << endl; // 回到起点
}

void solve() {
    int path[N];
    for (int i = 0; i < N; ++i) {
        path[i] = i;
    }
    int ans = INF;
    do {
        int sum = 0;
        for (int i = 0; i < N - 1; ++i) {
            if (graph[path[i]][path[i+1]] == INF) {
                sum = INF;
                break;
            }
            sum += graph[path[i]][path[i+1]];
        }
        if (graph[path[N-1]][path[0]] != INF) {
            sum += graph[path[N-1]][path[0]]; // 回到起点
        } else {
            sum = INF;
        }
        if (sum < ans) {
            ans = sum;
            print(path);
        }
    } while (next_permutation(path, path + N));
    cout << "最短路线长度为：" << ans << endl;
}

int main() {
    srand(time(NULL));
    solve();
    return 0;
}

该代码中，我们通过 `graph` 数组存储了城市地图，其中 `INF` 表示两点之间没有连通。`solve` 函数通过枚举所有可能的路径，并计算路径长度，来找到最短路径。在计算路径长度时，如果某个点与下一个点之间没有连通，则路径长度为 INF。最后我们通过 `print` 函数打印路径，通过 `ans` 变量保存最短路径长度。