c++ - 找到气体容器的最小必要体积

Question

我在比赛的某个地方发现了这个问题，但还没有想出解决方案。

There is the N cities with coordinates (x, y). I have to go from first city and reach the second city. There is a gas station in each city. So I have to find minimum necessary volume of gas container to reach the final city. For example:

Input:
3
17 4
19 4
18 5
Output:
1.414

在这里，我的方法是:1->3->2

我正在使用简单的暴力破解方法，但速度太慢了。如何优化我的代码？也许有更好的解决方案？

#include <iostream>
#include <algorithm>
#include <stack>
#include <math.h>
#include <cstring>
#include <iomanip>
#include <map>
#include <queue>
#include <fstream>
using namespace std;

int n, used[203];

double min_dist;

struct pc {
    int x, y;
};

pc a[202];

double find_dist(pc a, pc b) {
    double dist = sqrt( (a.x - b.x)*(a.x - b.x) + (a.y - b.y)*(a.y - b.y) );
    return dist;
}

void functio(double d, int used[], int k, int step) {
    used[k] = 1;
    if(k == 1) {
        if(d < min_dist) {
            min_dist = d;
        }
        used[k] = 0;
        return;
    }

    for(int i = 1; i < n; ++i) {
        if(i != k && used[i] == 0) {
            double temp = find_dist(a[k], a[i]);

            if(temp > d) {
                if(temp < min_dist)
                functio(temp, used, i, step + 1);
            }
            else {
                if(d < min_dist)
                functio(d, used, i, step + 1);
            }
        }
    }
    used[k] = 0;
}

int main() {

    cin >> n;

    for(int i = 0; i < n; ++i)
        cin >> a[i].x >> a[i].y;

    min_dist = 1000000;
    memset(used, 0, sizeof(used));
    functio(0, used, 0, 0);
    cout << fixed  << setprecision(3) << min_dist << endl;
}

Answer 1

最小生成树具有对顶点之间的所有路径进行编码的整洁属性，从而最小化路径上最长边的长度。对于 Euclidean MST，您可以计算 Delaunay 三角剖分，然后运行您最喜欢的 O(m log n) 时间算法(在具有 m = O(n) 条边的图上)，总运行时间为 O(n log n)。或者，您可以使用简单的优先级队列运行 Prim，以获得具有良好常数的 O(n^2) 时间算法(特别是如果您利用 SIMD)。