本题在洛谷上的链接：
应该算NOIP2017里比较简单的。。。
一开始以为水上了天，直接用邻接矩阵存边，结果TLE了两个点，改成邻接链表就过了。应该是多组输入数据的原因。
这道题需要注意的是溢出错误，虽然坐标不会炸int，但中间的运算过程会，所以有的地方要用long long。
1 #include2 #include 3 #include 4 #include 5 6 using namespace std; 7 8 typedef long long ll; 9 10 const int maxn = 1005;11 12 int head[maxn], eid;13 14 struct Edge {15 int v, next;16 } edge[maxn / 2 * maxn];17 18 void insert(int u, int v) {19 edge[++eid].v = v;20 edge[eid].next = head[u];21 head[u] = eid;22 }23 24 int t, n, h, r;25 int x[maxn], y[maxn], z[maxn], vis[maxn];26 27 queue q;28 29 inline ll pw2(int x) { return 1LL * x * x;}30 31 inline double dis(int i, int j) {32 return sqrt(pw2(x[i] - x[j]) + pw2(y[i] - y[j]) + pw2(z[i] - z[j]));33 }34 35 inline int bfs() {36 q.push(0);37 vis[0] = 1;38 while (!q.empty()) {39 int u = q.front();40 q.pop();41 if (u == n + 1) {42 while (!q.empty()) q.pop();43 return 1;44 }45 vis[u] = 1;46 for (int p = head[u]; p; p = edge[p].next)47 if (!vis[edge[p].v]) q.push(edge[p].v);48 }49 return 0;50 }51 52 int main() {53 scanf("%d", &t);54 while (t--) {55 memset(vis, 0, sizeof(vis));56 memset(head, 0, sizeof(head));57 eid = 0;58 scanf("%d%d%d", &n, &h, &r);59 for (int i = 1; i <= n; ++i) {60 scanf("%d%d%d", &x[i], &y[i], &z[i]);61 if (abs(z[i]) <= r) {insert(0, i); insert(i, 0);}62 if (abs(1LL * h - z[i]) <= r) {insert(n + 1, i); insert(i, n + 1);}63 }64 for (int i = 1; i <= n; ++i)65 for (int j = i + 1; j <= n; ++j)66 if (dis(i, j) <= 2 * r)67 {insert(i, j); insert(j, i);}68 if (bfs()) printf("Yes\n");69 else printf("No\n");70 }71 return 0;72 }