甲乙两人同时从A地出发要尽快同时赶到B地。出发时A地有一辆小车,可是这辆小车除了驾驶员外只能带一人。已知甲、乙两人的步行速度一样,且小于车的速度。问:怎样利用小车才能使两人尽快同时到达。c语言分治法

这是一个经典的分治问题，可以采用递归的方法求解。

具体思路如下：

1. 如果甲和乙的出发地点相同，那么他们可以一起坐车到达终点，此时用时为车的行驶时间。

2. 如果甲和乙的出发地点不同，可以假设甲先坐车前往乙的出发地点，然后甲和乙一起坐车到达终点。

3. 对于甲先坐车到乙出发地点的情况，可以递归求解，即将问题转化为从甲出发到乙出发地点的情况。

4. 对于乙先坐车到甲出发地点的情况同理。

5. 在递归求解过程中，需要注意不能重复计算，可以使用备忘录方法或动态规划方法来优化算法。

下面是使用C语言实现的代码：

#include <stdio.h>
#include <stdlib.h>

#define MAXN 100
#define INF 0x3f3f3f3f

int n;  // 出发点个数
int dist[MAXN][MAXN];  // 距离矩阵
int memo[MAXN][MAXN];  // 备忘录

int solve(int a, int b) {
    if (memo[a][b] != INF) return memo[a][b];  // 已经计算过，直接返回备忘录中的值

    int ans = INF;
    for (int k = 0; k < n; k++) {
        // 枚举所有可能的中转点
        if (a != k && b != k && dist[a][k] != INF && dist[k][b] != INF) {
            int tmp = dist[a][k] + dist[k][b];
            if (tmp < dist[a][b]) {
                // 如果中转更快，则更新答案
                ans = tmp;
            } else {
                ans = dist[a][b];
            }
        }
    }

    memo[a][b] = ans;
    memo[b][a] = ans;
    return ans;
}

int main() {
    int m;  // 边数
    scanf("%d%d", &n, &m);

    // 初始化距离矩阵和备忘录
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            dist[i][j] = INF;
            memo[i][j] = INF;
        }
        dist[i][i] = 0;
        memo[i][i] = 0;
    }

    // 读入边权
    for (int i = 0; i < m; i++) {
        int u, v, w;
        scanf("%d%d%d", &u, &v, &w);
        dist[u][v] = w;
        dist[v][u] = w;
    }

    // Floyd求解距离矩阵
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF) {
                    dist[i][j] = dist[i][j] < dist[i][k] + dist[k][j] ? dist[i][j] : dist[i][k] + dist[k][j];
                }
            }
        }
    }

    // 递归求解
    int ans = INF;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i != j) {
                int tmp = solve(i, j) + dist[0][i] + dist[0][j];
                ans = ans < tmp ? ans : tmp;
            }
        }
    }

    printf("%d\n", ans);
    return 0;
}