Untitled

unknown
plain_text
11 days ago
1.9 kB
0
Indexable
Never
```#include <iostream>
using namespace std;

int T, tc;
int N;
int XYR[205][3];
int map[205][205];
int dist[205];
int visit[205];

#define INF 10000000
#define MINF(a,b) a<=b?a:b
#define STEP(d) d<=40?1:1000

void init_dist(){
for(int i=0; i<N; i++){
dist[i] = INF;
}
}

void clr_visit(){
for(int i=0; i<N; i++){
visit[i]=0;
}
}

int isVisitAll(){
for(int i=0; i<N; i++){
if(visit[i]==0)
return 0;
}
return 1;
}

int sqrt(int input){
int ans=0;
for(int i=0; i<=input; i++){
if(i*i>input){
ans=i-1;
break;
}
}
if((input-ans*ans)!=0){
ans++;
}
return ans;
}

int main()
{
freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
cin >> T;
for(tc=1; tc<=T; tc++)
{
cin >> N;
for(int i=0; i<N; i++){
cin >> XYR[i][0] >> XYR[i][1] >> XYR[i][2];
}
for(int i=0; i<N; i++)
{
for(int j=i; j<N; j++)
{
if(i==j)
map[i][j]=map[j][i]=0;
else{
int a = XYR[i][0] - XYR[j][0];
int b = XYR[i][1] - XYR[j][1];
int d = sqrt(a*a+b*b)-XYR[i][2]-XYR[j][2];
if (d <= 40) {
map[i][j] = map[j][i] = 1;
} else if (d > 40 && d <= 90) {
map[i][j] = map[j][i] = 1000;
} else {
map[i][j] = map[j][i] = -1;
}
}
}
}
//Solve
init_dist();
clr_visit();
dist[0]=0;
while(isVisitAll()==0)
{
int min = INF+1;
int cur=0;
for(int i=0; i<N; i++){
if(dist[i]<min && visit[i]==0){
min = dist[i];
cur = i;
}
}
visit[cur]=1;
for(int i=0; i<N; i++){
if (map[cur][i] == -1) continue;
if(i!=cur){
dist[i] = MINF(dist[i], dist[cur]+map[cur][i]);
}
}
}
if(dist[N-1]!=INF){
int long_jmp = dist[N-1] / 1000;
int short_jmp = dist[N-1] % 1000;
cout << long_jmp << " " << short_jmp << endl;
} else {
cout << -1 << endl;
}
//cout << endl;
}
return 0;
}
```