题解 | #激活锚点#

E. 激活锚点

知识点：最小生成树

对 个传送锚点的坐标建无向完全图，边权为两点间的距离。

求出最小生成树的权值。

再加上距离起点最近的传送锚点的距离，即为答案。

最小生成树用 Prim 算法（时间复杂度：）或 Kruskal 算法（时间复杂度：）都能过。

常见错误解法：把起点坐标和传送锚点的坐标放到一起跑最小生成树。

似乎还有高级做法，显然超纲了，不讲了。

标程

C++

#include <bits/stdc++.h>

using namespace std;

using ll = long long;

constexpr double INF = 1e18;

struct Point
{
    int x, y;
};

double dist(const Point &p1, const Point &p2)
{
    return hypot(p1.x - p2.x, p1.y - p2.y);
}

// Prim 算法求最小生成树
double prim(const vector<Point> &points)
{
    int n = points.size();
    vector<bool> visited(n);
    vector<double> min_dist(n, INF);
    min_dist[0] = 0;

    double res = 0;
    for (int i = 0; i < n; ++i)
    {
        int u = -1;
        for (int j = 0; j < n; ++j)
        {
            if (!visited[j] && (u == -1 || min_dist[j] < min_dist[u]))
            {
                u = j;
            }
        }

        visited[u] = true;
        res += min_dist[u];
        for (int v = 0; v < n; ++v)
        {
            if (!visited[v])
            {
                min_dist[v] = min(min_dist[v], dist(points[u], points[v]));
            }
        }
    }

    return res;
}

void solve()
{
    Point p0;
    cin >> p0.x >> p0.y;

    int n;
    cin >> n;
    vector<Point> points(n);
    for (auto &[x, y] : points)
    {
        cin >> x >> y;
    }

    double ans1 = prim(points); // 最小生成树
    double ans2 = INF; // 距离起点最近的点
    for (const auto &p : points)
    {
        ans2 = min(ans2, dist(p0, p));
    }
    double ans = ans1 + ans2;
    cout << ans << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cout.setf(ios::fixed);
    cout.precision(15);

    int T;
    cin >> T;
    while (T--)
    {
        solve();
    }
}

Java

import java.util.*;
import java.io.*;

public class Main {
    static Kattio io = new Kattio();

    static double dist(int x1, int y1, int x2, int y2) {
        int dx = x1 - x2;
        int dy = y1 - y2;
        return Math.hypot(dx, dy);
    }

    static double prim(int n, int[] x, int[] y) {
        double[] minDist = new double[n];
        boolean[] visited = new boolean[n];
        Arrays.fill(minDist, Double.MAX_VALUE);
        minDist[0] = 0;
        double ans = 0;
        for (int i = 0; i < n; ++i) {
            int u = -1;
            for (int j = 0; j < n; ++j) {
                if (!visited[j] && (u == -1 || minDist[j] < minDist[u])) {
                    u = j;
                }
            }
            visited[u] = true;
            ans += minDist[u];
            for (int v = 0; v < n; ++v) {
                if (!visited[v]) {
                    double d = dist(x[u], y[u], x[v], y[v]);
                    minDist[v] = Math.min(minDist[v], d);
                }
            }
        }
        return ans;
    }

    static void solve() {
        int x0 = io.nextInt();
        int y0 = io.nextInt();
        int n = io.nextInt();
        int x[] = new int[n];
        int y[] = new int[n];
        for (int i = 0; i < n; ++i) {
            x[i] = io.nextInt();
            y[i] = io.nextInt();
        }
        double ans1 = prim(n, x, y);
        double ans2 = Double.MAX_VALUE;
        for (int i = 0; i < n; ++i) {
            ans2 = Math.min(ans2, dist(x0, y0, x[i], y[i]));
        }
        double ans = ans1 + ans2;
        io.printf("%.15f\n", ans);
    }

    public static void main(String[] args) {
        int T = io.nextInt();
        while (T-- > 0) {
            solve();
        }

        io.close();
    }
}

class Kattio extends PrintWriter {
    private BufferedReader r;
    private StringTokenizer st;
    // 标准 IO
    public Kattio() { this(System.in, System.out); }
    public Kattio(InputStream i, OutputStream o) {
        super(o);
        r = new BufferedReader(new InputStreamReader(i));
    }
    // 在没有其他输入时返回 null
    public String next() {
        try {
            while (st == null || !st.hasMoreTokens())
                st = new StringTokenizer(r.readLine());
            return st.nextToken();
        } catch (Exception e) {}
        return null;
    }
    public int nextInt() { return Integer.parseInt(next()); }
    public double nextDouble() { return Double.parseDouble(next()); }
    public long nextLong() { return Long.parseLong(next()); }
}

Python

import math


def prim(points):
    res = 0.0
    n = len(points)
    dist = [math.inf] * n
    visited = [False] * n
    dist[0] = 0
    for _ in range(n):
        u = -1
        for i in range(n):
            if not visited[i] and (u == -1 or dist[i] < dist[u]):
                u = i
        visited[u] = True
        res += dist[u]
        for v in range(n):
            if not visited[v]:
                dist[v] = min(dist[v], math.hypot(points[u][0] - points[v][0], points[u][1] - points[v][1]))
    return res


def solve():
    x0, y0 = map(int, input().split())
    n = int(input())
    points = []
    for _ in range(n):
        x, y = map(int, input().split())
        points.append((x, y))
    dist = prim(points)
    # 牛客网的 Python 版本还不支持 math.dist，所以只能用 math.hypot
    ans = dist + min(math.hypot(x0 - pt[0], y0 - pt[1]) for pt in points)
    print(f"{ans:.15f}")


T = int(input())
for _ in range(T):
    solve()