# Untitled

unknown
plain_text
6 months ago
1.5 kB
1
Indexable
Never
```#include<iostream>
using namespace std;

int n;
int energy[1000][1000];
int minEnergy[1000];
int visit[1000],x[1000],y[1000],r[1000];

int calEnergy(int x1, int y1, int r1, int x2, int y2, int r2)
{
if( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) <= (40+r1+r2)*(40+r1+r2)) return 1;
else if( (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) <= (90+r1+r2)*(90+r1+r2)) return 200;
return 99999;
}

int main()
{
//freopen("input.txt","r",stdin);
int t;
cin >> t;
for (int tc = 1; tc<=t; tc++)
{
cin >> n;
for (int i=0 ; i<n; i++)
cin >> x[i] >> y[i] >> r[i];
for (int i=0; i<n; i++)
{
visit[i] = 0;
minEnergy[i] = 99999;
}

for (int i = 0; i<n; i++)
for (int j=0; j<n; j++)
{
if (i == j) energy[i][j] = 0;
else energy[i][j] = calEnergy(x[i],y[i],r[i],x[j],y[j],r[j]);
}
int selected = 0;
minEnergy[0] = 0;
int nearleaf, nearDist;
while (selected < n)
{
nearDist = 99999;
for (int i=0; i<n; i++)
if (visit[i] == 0 && minEnergy[i] < nearDist)
{
nearDist = minEnergy[i];
nearleaf = i;
}
if (nearDist == 99999||selected == n-1) break;
selected++;
visit[nearleaf] = 1;
for (int i=0; i<n;i++)
{
if (visit[i] == 0 && minEnergy[nearleaf] + energy[nearleaf][i] < minEnergy[i])
{
minEnergy[i] = minEnergy[nearleaf] + energy[nearleaf][i] ;
}
}
}
if (minEnergy[n-1] == 99999) cout << "-1" << endl;
else cout << minEnergy[n-1]/200 <<" " << minEnergy[n-1]%200 << endl;
}
return 0;
}
```