Untitled
unknown
plain_text
a year ago
1.3 kB
7
Indexable
#include<iostream> using namespace std; int a[200]; int b[200]; int c[200]; int visited[200]; int dis[200]; int n, max; int count1, count2; int tinhkhoangcach(int x1, int x2){ if((40+c[x1]+c[x2])*(40+c[x1]+c[x2])>=((a[x1]-a[x2])*(a[x1]-a[x2])+(b[x1]-b[x2])*(b[x1]-b[x2]))) return 1; else if((90+c[x1]+c[x2])*(90+c[x1]+c[x2])>=((a[x1]-a[x2])*(a[x1]-a[x2])+(b[x1]-b[x2])*(b[x1]-b[x2]))) return 200; return 1000000; } void search(int x, int step){ //if(x==n-1) return; if(step== n-1) return; for(int i=0; i<n; i++){ if(i!=x){ int h = tinhkhoangcach(x, i); if((dis[x]+h)<dis[i]) dis[i] = dis[x]+h; } } int min = 1000000; int g=0; for(int i=1; i<n; i++){ if(dis[i]<min && visited[i]==0){ min = dis[i]; g = i; } } if(g>0){ visited[g]=1; search(g,step+1); } } int main(){ //freopen("in.txt","r", stdin); int t; cin>>t; for(int tc=1; tc<=t; tc++){ cin>>n; for(int i=0; i<n; i++){ cin>>a[i]>>b[i]>>c[i]; dis[i] = 1000000; visited[i] = 0; } dis[0] = 0; count1 = 0; count2=0; int result=0; visited[0] = 1; search(0,0); if(dis[n-1]==1000000) cout<<"-1"<<endl; else cout<<dis[n-1]/200<<" "<<dis[n-1]%200<<endl; } return 0; }
Editor is loading...