答案:<pre class="brush:cpp;toolbar:false">#include <iostream>
#include <vector>
#include <cmath>
#include <iomanip>
#include <algorithm>
using namespace std;
typedef long long ll;
const double INF = 1e18;
const double eps = 1e-8;
struct Point {
ll x, y;
Point() {}
Point(ll x_, ll y_) : x(x_), y(y_) {}
};
struct Circle {
ll x, y, r;
Circle() {}
Circle(ll x_, ll y_, ll r_) : x(x_), y(y_), r(r_) {}
};
// 两点距离
double dis_pp(const Point& a, const Point& b) {
ll dx = a.x - b.x;
ll dy = a.y - b.y;
return sqrt(1.0 * dx * dx + 1.0 * dy * dy);
}
// 点到圆的暴露长度,点在圆内返回0
double dis_pc(const Point& p, const Circle& c) {
double d = dis_pp(p, Point(c.x, c.y));
if (d <= c.r + eps) return 0.0;
return d - c.r;
}
// 两个圆之间暴露长度,相交/包含返回0
double dis_cc(const Circle& a, const Circle& b) {
double d = dis_pp(Point(a.x, a.y), Point(b.x, b.y));
double sumr = a.r + b.r;
if (d <= sumr + eps) return 0.0;
return d - sumr;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout << fixed << setprecision(10);
ll xs, ys, xt, yt;
cin >> xs >> ys >> xt >> yt;
Point S(xs, ys), T(xt, yt);
int N;
cin >> N;
vector<Circle> cir(N);
for (int i = 0; i < N; i++) {
cin >> cir[i].x >> cir[i].y >> cir[i].r;
}
// 总点数:0起点,1~N护盾,N+1终点
int tot = N + 2;
vector<vector<double>> g(tot, vector<double>(tot, INF));
for (int i = 0; i < tot; i++) g[i][i] = 0;
// 0(S) <-> N+1(T)
g[0][N+1] = dis_pp(S, T);
g[N+1][0] = dis_pp(S, T);
// 0(S) 和所有护盾 1~N
for (int i = 1; i <= N; i++) {
double d = dis_pc(S, cir[i-1]);
g[0][i] = d;
g[i][0] = d;
}
// N+1(T) 和所有护盾 1~N
for (int i = 1; i <= N; i++) {
double d = dis_pc(T, cir[i-1]);
g[N+1][i] = d;
g[i][N+1] = d;
}
// 护盾之间 i,j (1~N)
for (int i = 1; i <= N; i++) {
for (int j = i + 1; j <= N; j++) {
double d = dis_cc(cir[i-1], cir[j-1]);
g[i][j] = d;
g[j][i] = d;
}
}
// Floyd 求全源最短路,N<=1000 tot=1002,1e9?不行!换Dijkstra单源
vector<double> dist(tot, INF);
vector<bool> vis(tot, false);
dist[0] = 0;
for (int step = 0; step < tot; step++) {
int u = -1;
double minv = INF;
for (int i = 0; i < tot; i++) {
if (!vis[i] && dist[i] < minv) {
minv = dist[i];
u = i;
}
}
if (u == -1) break;
vis[u] = true;
for (int v = 0; v < tot; v++) {
if (g[u][v] < INF && dist[v] > dist[u] + g[u][v]) {
dist[v] = dist[u] + g[u][v];
}
}
}
cout << dist[N+1] << endl;
return 0;
}</pre>
这道题暂未补解析。