Untitled
unknown
plain_text
10 months ago
2.2 kB
3
Indexable
Never
#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; }