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; }
Leave a Comment