集合位置(Meeting Location) 题解

算法分析

先在无向欧几里得距离图上跑一次 Dijkstra，求出 $1$ 到 $n$ 的最短路径并记录前驱边。由于边权均大于 $0$，最短路径与删边后的新最短路径均天然为简单路径（不重复经过顶点）；枚举最短路上的每条边将其临时屏蔽，重新跑 Dijkstra 取 $1$ 到 $n$ 最短路长度的最小值即可（若存在多条并列最短路会自动得到相同最短长度，若全部不可达则输出 -1）。总时间复杂度 $O(n(n^2 + m \log n))$。

参考代码

#include <bits/stdc++.h>
using namespace std;

struct Edge {
    int to, id;
    double w;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m)) return 0;
    vector<double> x(n + 1), y(n + 1);
    for (int i = 1; i <= n; ++i) cin >> x[i] >> y[i];
    vector<vector<Edge>> g(n + 1);
    int eid = 0;
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        if (u == v || u < 1 || u > n || v < 1 || v > n) continue;
        double w = hypot(x[u] - x[v], y[u] - y[v]);
        ++eid;
        g[u].push_back({v, eid, w});
        g[v].push_back({u, eid, w});
    }
    if (n == 1) {
        cout << -1 << "\n";
        return 0;
    }
    const double INF = 1e18;
    vector<int> preV(n + 1, -1), preE(n + 1, -1);
    auto dijkstra = [&](int banId, bool rec) -> double {
        vector<double> dist(n + 1, INF);
        priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
        dist[1] = 0.0;
        pq.push({0.0, 1});
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            if (d > dist[u] + 1e-11) continue;
            if (u == n) break;
            for (const auto& e : g[u]) {
                if (e.id == banId) continue;
                if (dist[u] + e.w + 1e-11 < dist[e.to]) {
                    dist[e.to] = dist[u] + e.w;
                    if (rec) {
                        preV[e.to] = u;
                        preE[e.to] = e.id;
                    }
                    pq.push({dist[e.to], e.to});
                }
            }
        }
        return dist[n];
    };
    double d1 = dijkstra(-1, true);
    if (d1 >= INF / 2) {
        cout << -1 << "\n";
        return 0;
    }
    vector<int> pathEdges;
    for (int cur = n; cur != 1 && cur != -1; cur = preV[cur]) {
        pathEdges.push_back(preE[cur]);
    }
    double ans = INF;
    for (int id : pathEdges) {
        ans = min(ans, dijkstra(id, false));
    }
    if (ans >= INF / 2) {
        cout << -1 << "\n";
    } else {
        cout << fixed << setprecision(2) << ans << "\n";
    }
    return 0;
}