c++ 三维点群最短路径 源代码

以下是一个简单的 c++ 三维点群最短路径的实现示例：

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>

using namespace std;

const int MAXN = 10005;
const double INF = 1e9;

struct Point {
    double x, y, z;
    Point(double x = 0, double y = 0, double z = 0): x(x), y(y), z(z) {}
};

struct Edge {
    int v;
    double w;
    Edge(int v = 0, double w = 0): v(v), w(w) {}
};

vector<Edge> G[MAXN];
double d[MAXN];
bool vis[MAXN];

double dist(Point& p1, Point& p2) {
    double dx = p1.x - p2.x, dy = p1.y - p2.y, dz = p1.z - p2.z;
    return sqrt(dx * dx + dy * dy + dz * dz);
}

void dijkstra(int s, int n) {
    fill(d, d + n, INF);
    fill(vis, vis + n, false);
    d[s] = 0;
    priority_queue<pair<double, int>, vector<pair<double, int> >, greater<pair<double, int> > > q;
    q.push(make_pair(0, s));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = 0; i < G[u].size(); i++) {
            int v = G[u][i].v;
            double w = G[u][i].w;
            if (d[v] > d[u] + w) {
                d[v] = d[u] + w;
                q.push(make_pair(d[v], v));
            }
        }
    }
}

int main() {
    int n;
    cin >> n;
    vector<Point> points(n);
    for (int i = 0; i < n; i++) {
        cin >> points[i].x >> points[i].y >> points[i].z;
        for (int j = 0; j < i; j++) {
            double w = dist(points[i], points[j]);
            G[i].push_back(Edge(j, w));
            G[j].push_back(Edge(i, w)); // 无向图
        }
    }
    dijkstra(0, n);
    cout << d[n - 1] << endl;
    return 0;
}

这段代码使用了 Dijkstra 算法来计算从起点到终点的最短路径。其中，点之间的距离使用欧几里得距离来计算。输入格式为每行三个浮点数，表示一个三维点的坐标。第一行表示点的数量，最后一行输出从起点到终点的最短距离。