NIOP 求条
查看原帖
NIOP 求条
1238483
cqbzzlr楼主2024/8/16 09:57
#include <bits/stdc++.h>

using namespace std;

const int N = 1005;

vector <int> v[N];
queue <int> q;
bool fg;
int n,h,r;
bool vis[N];
int x[N],y[N],z[N];

long long dist(int a,int b,int c,int a1,int b1,int c1)
{
	return sqrt((a - a1) * (a - a1) + (b - b1) * (b - b1) + (c - c1) * (c - c1)) + 0.9999;
}


int main()
{
	int T;
	cin >> T;
	while(T--)
	{
		while(!q.empty()) q.pop();
		fg = false;
		scanf("%d %d %d",&n,&h,&r);
		for(int i = 1;i <= n;i++)
		{
			scanf("%d%d%d",&x[i],&y[i],&z[i]);
			while(v[i].size()) v[i].pop_back();
			vis[i] = 0;
		}
		v[0].clear();
		while(v[0].size()) v[0].pop_back();
		vis[0] = 0;
		v[n + 1].clear();
		while(v[n + 1].size()) v[n + 1].pop_back();
		vis[n + 1] = 0;
		for(int i = 1;i <= n;i++)
		{
			for(int j = i + 1;j <= n;j++)
			{
				if(dist(x[i],y[i],z[i],x[j],y[j],z[j]) <= 2 * r)
				{
					v[i].push_back(j);
					v[j].push_back(i);
				}
			}
			if(z[i] + r >= h)
			{
				v[i].push_back(n + 1);
			}
			if(z[i] - r <= 0)
			{
				v[0].push_back(i);
			}
		}
		q.push(0);
		while(!q.empty())
		{
			int x = q.front();
			if(x == n + 1)
			{
				fg = true;
				break;
			}
			q.pop();
			for(int i = 0;i < v[x].size();i++)
			{
				int y = v[x][i];
				q.push(y);
			}
		}
		if(fg)  cout << "Yes";
		else cout << "No";
		cout << endl;
	}
}

tlq说的剪枝也加了,但是不知道为啥会TLE

2024/8/16 09:57
加载中...