Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
2.2 kB
3
Indexable
#include<stdio.h>
#include<iostream>

#define MAX_N 1002
#define MAX_QUEUE 10002
#define INF 999999999

using namespace std;

template <class T> class queue{
private:
	int index_front;
	int index_rear;
	T qu[MAX_QUEUE];
public:
	queue();
	T front();
	bool empty();
	void pop();
	void push(T x);
	void reset();

};

template <class T> queue<T>::queue(){
	index_front = -1;
	index_rear = -1;
};

template<class T> void queue<T>::push(T x){
	if (index_front == -1){
		index_front++;
	}
	index_rear++;
	qu[index_rear] = x;
};

template<class T> void queue<T>::pop(){
	index_front++;
};

template<class T> T queue<T>::front(){
	return qu[index_front];
};

template<class T> bool queue<T>::empty(){
	return index_front == -1 || index_front > index_rear;
};

template<class T> void queue<T>::reset(){
	index_front = -1;
	index_rear = -1;
};


int x[MAX_N], y[MAX_N], r[MAX_N];
int n;
int a[MAX_N][MAX_N];
int d[MAX_N];
bool processed[MAX_N];

int res;
int cnt_edge;


queue<int> q1;

int main(){
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	int t;
	cin >> t;
	int tc = 1;
	while (t--){
		cin >> n;
		for (int i = 0; i < n; i++){
			cin >> x[i] >> y[i] >> r[i];
		}
		for (int i = 0; i < n; i++){
			for (int j = 0; j < n; j++){
				int tmp = (x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]);
				if (tmp > (r[i] + r[j] + 90) * (r[i] + r[j] + 90))
					a[i][j] = INF;
				else if(tmp >= (r[i] + r[j] + 40) * (r[i] + r[j] + 40))
					a[i][j] = 200;
				else a[i][j] = 1;
			}
		}
		d[0] = 0;
		processed[0] = false;
		for (int i = 1; i < n; i++){
			d[i] = INF;
			processed[i] = false;
		}

		for (int i = 0; i < n; i++){
			int _min = INF; 
			int v = -1;
			for (int j = 0; j < n; j++){
				if ((_min > d[j] || v == -1) && !processed[j])
					v = j, _min = d[j];
			}

			processed[v] = true;
			for (int j = 0; j < n; j++){
				d[j] = min(d[j], d[v] + a[v][j]);
			}
		}

		if (d[n - 1] == INF)
			cout << -1 << endl;
		else cout << d[n - 1] / 200 << " " << d[n - 1] % 200 << endl;
		//printf("Case #%d\n%d\n", tc++, res);

	}	
	return 0;
}