求多个点之间的最短距离用分治法c++

在C++中，求解多个点之间的最短距离问题，通常涉及到计算两点间的欧几里得距离，如果有多组点需要处理，可以使用分治策略，比如Kruskal算法（适用于连通图），用于找到给定点集的最小生成树，树的边长即为所有点对的最短路径之和。

不过，如果你问的是如何直接找出每一对点之间的最短距离，而不是整体上的最优化结构，那么可以使用邻接矩阵或邻接表来存储点与点之间的距离，并遍历所有可能的配对。例如，可以用Dijkstra算法（单源最短路径算法）逐次更新每个节点到起点的距离，直到达到所有节点。

以下是简化版的Dijkstra算法伪代码：

#include <vector>
#include <queue>

// 使用优先队列存放待处理节点及其距离
struct Node {
    int dist, index;
    bool operator<(const Node& other) const { return dist < other.dist; }
};

std::vector<int> dijkstra(std::vector<std::pair<int, int>>& graph, int src) {
    int n = graph.size();
    std::priority_queue<Node> pq;
    std::vector<int> dist(n, INT_MAX);
    dist[src] = 0;

    for (int i = 0; i < n; ++i) {
        // 从距离已知的最近节点开始
        Node current = pq.top(); pq.pop();
        if (dist[current.index] != INT_MAX) continue;

        // 遍历当前节点的所有邻居
        for (auto [dst, weight] : graph[current.index]) {
            if (dist[dst] > dist[current.index] + weight) {
                dist[dst] = dist[current.index] + weight;
                pq.push({dist[dst], dst});
            }
        }
    }

    return dist;
}

这里`graph`是一个二维数组或邻接表表示，其中`graph[i][j]`代表点`i`到点`j`的距离。这个函数会返回一个长度为n的向量，其中`dist[i]`就是点i到所有其他点的最短距离。