一个售货员要到若干个村庄去售货，村庄间的道路是已知的。如果售货员 从商店出发到每个村庄售货一次，然后返回商店，那么他应该选择一条什么样的路线方能使所走的路程最短，用回溯法写出累C语言代码

以下是基于回溯法的 C 语言代码实现：

#include <stdio.h>
#include <limits.h>

#define N 5

// 村庄数量
int n = N;
// 村庄到商店的距离
int distance[N+1][N+1] = {
    {0, 2, 5, 7, 3},
    {2, 0, 6, 4, 5},
    {5, 6, 0, 9, 8},
    {7, 4, 9, 0, 1},
    {3, 5, 8, 1, 0},
};
// 标记每个村庄是否已经被访问过
int visited[N+1] = {0};
// 记录路径
int path[N+1] = {0};
// 记录最短路径
int shortest_path[N+1] = {0};
// 记录当前路径长度
int current_length = 0;
// 记录最短路径长度
int shortest_length = INT_MAX;

void tsp(int pos) {
    // 回溯终止条件
    if (pos == n) {
        // 更新最短路径
        if (current_length + distance[path[n-1]][1] < shortest_length) {
            shortest_length = current_length + distance[path[n-1]][1];
            for (int i = 0; i <= n; i++) {
                shortest_path[i] = path[i];
            }
        }
        return;
    }
    
    // 对于每个村庄，尝试将其加入路径
    for (int i = 2; i <= n; i++) {
        if (!visited[i]) {
            visited[i] = 1;
            path[pos] = i;
            current_length += distance[path[pos-1]][i];
            // 剪枝，如果当前路径长度已经大于最短路径，那么不必继续搜索
            if (current_length < shortest_length) {
                tsp(pos+1);
            }
            current_length -= distance[path[pos-1]][i];
            visited[i] = 0;
        }
    }
}

int main() {
    visited[1] = 1;
    path[0] = 1;
    
    tsp(1);
    
    printf("最短路径长度为: %d\n", shortest_length);
    printf("最短路径为: ");
    for (int i = 0; i <= n; i++) {
        printf("%d ", shortest_path[i]);
    }
    printf("\n");
    
    return 0;
}

在上面的代码中，我们使用了五个全局变量：`n` 表示村庄数量，`distance` 二维数组表示每两个村庄之间的距离，`visited` 数组表示每个村庄是否已经被访问过，`path` 数组用于记录路径，`shortest_path` 数组用于记录最短路径。

在 `tsp` 函数中，我们使用了一个 `pos` 变量来表示当前正在访问的村庄的位置，从 1 开始，一直到 n。对于每个村庄，我们尝试将其加入路径中，并更新当前路径长度。如果当前路径长度已经大于最短路径长度，那么不必继续搜索，直接返回。如果当前路径已经包含了所有村庄，那么更新最短路径，并返回。

最后，我们输出最短路径长度和最短路径。