旅行商问题C语言代码

旅行商问题是一个经典的组合优化问题，它是指给定一系列城市和每对城市之间的距离，求解访问每一个城市一次并返回起始城市的最短回路。该问题属于NP难问题，目前还没有找到多项式时间内求解该问题的算法。

以下是一个简单的旅行商问题的C语言代码，采用了暴力枚举的方式，时间复杂度为O(n!)：

#include <stdio.h>
#define MAXN 20
#define INF 0x3f3f3f3f

int n, m, ans = INF;
int map[MAXN][MAXN], vis[MAXN];

void dfs(int x, int sum, int cnt)
{
    if(cnt == n && sum + map[x] < ans)
    {
        ans = sum + map[x];
        return;
    }
    for(int i = 2; i <= n; i++)
    {
        if(!vis[i] && sum + map[x][i] < ans)
        {
            vis[i] = 1;
            dfs(i, sum + map[x][i], cnt+1);
            vis[i] = 0;
        }
    }
}

int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(i != j) map[i][j] = INF;
    for(int i = 1; i <= m; i++)
    {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        map[u][v] = map[v][u] = w;
    }
    vis = 1;
    dfs(1, 0, 1);
    printf("%d\n", ans);
    return 0;
}

该代码实现了一个深度优先搜索，通过vis数组来记录已经走过的城市，用sum来记录当前路径长度，cnt来记录已经走过的城市数。当所有城市都被访问一次时，如果当前路径长度小于ans，则更新ans的值。