思路与算法

先去掉半径更小且价格不低的劣质盘，保留半径与费用递增的类型。状态为桩及盘类型；同桩升级只补价差，跨桩只转到能相交的最小半径盘并付完整价格。下岸可触及的盘为起点，上岸可触及者为终点，跑Dijkstra。

正确性说明

同桩只需购买最大盘，其余盘完全被包含。某个跨桩选择若更大，可以先到最小可行盘再原地升级，费用不变；升级也保持此前所有相交关系。因此状态图恰好表达最优连接链，所有边非负，Dijkstra最短路就是最小花费。

复杂度

设桩N、类型M。排序O(MlogM)，距离预处理O(N²)，至多NM状态、O(N²M)候选边；二分类型及堆操作总O(N²M(logM+log(NM)))时间。空间含距离、状态及堆最坏O(N²+NM+N²M)，初始化计入。

易错点

岸边用竖直距离；圆盘相切也算相交。坐标大时平方用128位，开方初值须经整数平方校正。不可能连接输出原题失败标志。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n, m;
        long long W;
        cin >> n >> m >> W;
        vector<long long> x(n), y(n);
        for (int i = 0; i < n; i++)
            cin >> x[i] >> y[i];
        vector<pair<long long, long long>> types(m);
        for (auto &a : types)
            cin >> a.first >> a.second;
        sort(types.begin(), types.end());
        vector<pair<long long, long long>> keep;
        long long best = LLONG_MAX;
        for (int i = m - 1; i >= 0; i--)
            if (types[i].second < best) {
                best = types[i].second;
                keep.push_back(types[i]);
            }
        reverse(keep.begin(), keep.end());
        m = keep.size();
        vector<long long> R(m), C(m);
        for (int j = 0; j < m; j++) {
            R[j] = keep[j].first;
            C[j] = keep[j].second;
        }
        vector<vector<long long>> need(n, vector<long long>(n));
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                long long dx = x[i] - x[j], dy = y[i] - y[j], sq = dx * dx + dy * dy,
                          z = sqrtl((long double)sq);
                while ((__int128)z * z < sq)
                    z++;
                while (z && (__int128)(z - 1) * (z - 1) >= sq)
                    z--;
                need[i][j] = z;
            }
        const long long INF = 1LL << 60;
        vector<long long> d(n * m, INF);
        priority_queue<pair<long long, int>, vector<pair<long long, int>>,
                       greater<pair<long long, int>>>
            q;
        auto put = [&](int v, long long z) {
            if (z < d[v]) {
                d[v] = z;
                q.push({z, v});
            }
        };
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (R[j] >= y[i])
                    put(i * m + j, C[j]);
        long long ans = INF;
        while (!q.empty()) {
            auto z = q.top();
            q.pop();
            if (d[z.second] != z.first)
                continue;
            int i = z.second / m, j = z.second % m;
            if (R[j] >= W - y[i]) {
                ans = z.first;
                break;
            }
            if (j + 1 < m)
                put(i * m + j + 1, z.first + C[j + 1] - C[j]);
            for (int k = 0; k < n; k++)
                if (k != i) {
                    int t = lower_bound(R.begin(), R.end(), need[i][k] - R[j]) - R.begin();
                    if (t < m)
                        put(k * m + t, z.first + C[t]);
                }
        }
        if (ans == INF)
            cout << "impossible\n";
        else
            cout << ans << '\n';
    }
}