Untitled
unknown
plain_text
21 days ago
1.6 kB
0
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS #include<iostream> using namespace std; #define MAX 1000000000 int Map[201][201]; int visited[201], dist[201], R[201]; int xy[201][2]; int nTestcase, N, Min, min_index; int main() { freopen("input.txt","r",stdin); cin >> nTestcase; for (int testcase = 1; testcase <= nTestcase; testcase++) { cin >> N; for (int i = 0; i < N; i++) { visited[i] = 0; dist[i] = MAX; } dist[0] = 0; for (int i = 0; i < N; i++) { cin >> xy[i][0] >> xy[i][1] >> R[i]; } for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int value = (xy[j][0] - xy[i][0]) * (xy[j][0] - xy[i][0]) + (xy[j][1] - xy[i][1]) * (xy[j][1] - xy[i][1]); if (value > (90 + R[i] + R[j]) * (90 + R[i] + R[j])) { Map[i][j] = MAX; }else if (value > (40 + R[i] + R[j]) * (40 + R[i] + R[j])) { Map[i][j] = 200; } else if (value == 0) { Map[i][j] = 0; }else { Map[i][j] = 1; } } } for (int i = 0; i < N - 1; i++) { Min = MAX; for (int j = 0; j < N; j++) { if (!visited[j] && dist[j] <= Min) { Min = dist[j]; min_index = j; } } visited[min_index] = 1; for (int v = 0; v < N; v++) { if (!visited[v] && dist[min_index] != MAX && dist[v] > dist[min_index] + Map[min_index][v]) { dist[v] = dist[min_index] + Map[min_index][v]; } } } if (dist[N - 1] == MAX) { cout << -1 << endl; } else { cout << dist[N - 1] / 200 << " " << dist[N - 1] % 200 << endl; } } return 0; }