Untitled
plain_text
a month ago
2.4 kB
1
Indexable
Never
import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.PrintStream; import java.util.Scanner; public class CopyOfTheFrog { static { try { System.setIn(new FileInputStream("src/inp.txt")); // System.setOut(new PrintStream("src/out.txt")); } catch (FileNotFoundException e) { // TODO Auto-generated catch block e.printStackTrace(); } } static Scanner scanner = new Scanner(System.in); static void exec(int test) { int n=Integer.parseInt(scanner.next()); int[] x=new int[n],y=new int[n],r=new int[n]; for(int u=0;u<n;++u){ x[u]=Integer.parseInt(scanner.next()); y[u]=Integer.parseInt(scanner.next()); r[u]=Integer.parseInt(scanner.next()); } long cost[][]=new long[n][n]; //khoi tao ma tran trong so //kiem tra xem khoang cach giua 2 la sen tru ban kinh giua 2 la sen //<=40 => nhay gan dat la 1 //<=90 => nhay xa dat la n (do neu nhay gan vs trong so 1 thi chi nhay toi da n-1 lan, trong so toi da la n-1 => de chia du sau nay for(int u=0;u<n;++u) for(int v=0;v<n;++v) if(u!=v){ long c2=(x[u]-x[v])*(x[u]-x[v])+(y[u]-y[v])*(y[u]-y[v]); long right=(40+r[u]+r[v])*(40+r[u]+r[v]); long right2=(90+r[u]+r[v])*(90+r[u]+r[v]); if(c2<=right) cost[u][v]=1; else if(c2<=right2) cost[u][v]=n; } //dijktra tim quang duong ngan nhat //do trong quang duong ngan nhat thi trong so cua trong luong xa chiem dang ke //nen tim qdnn tuong ung vs so buoc di vs trog so max nho nhat boolean[] M=new boolean[n]; long[] res=new long[n]; for(int u=0;u<n;++u) res[u]=Long.MAX_VALUE; res[0]=0; for(int i=1;i<n;++i){ int u=-1; long costu=Long.MAX_VALUE; for(int v=0;v<n;++v) if(!M[v] && costu>res[v]){ costu=res[v]; u=v; } if(u==-1) break; M[u]=true; for(int v=0;v<n;++v) if(!M[v] && cost[u][v]>0 && res[v]>costu+cost[u][v]) res[v]=costu+cost[u][v]; } //so quang duong vs trong so max*trong so max + so qd trong so min if(res[n-1]==Long.MAX_VALUE) System.out.println(-1); else System.out.printf("%d %d\n",res[n-1]/n,res[n-1]%n); } public static void main(String[] args) { int t = Integer.parseInt(scanner.next()); for (int test = 1; test <= t; ++test) exec(test); scanner.close(); } }