There is one spaceship. X and Y co-odinate of source of spaceship and destination spaceship is given. There are N number of warmholes each warmhole has 5 values.
First 2 values are starting co-ordinate of warmhole and after that value no. 3 and 4 represents ending co-ordinate of warmhole and last 5th value is represents cost to pass through this warmhole. Now these warmholes are bi-direction.
Now the to go from (x1,y1) to (x2,y2) is abs(x1-x2)+abs(y1-y2).
The main problem here is to find minimum distance to reach spaceship from source to destination co-ordinate using any number of warm-hole. It is ok if you wont use any warmhole.
class Samsung{
static int ans=Integer.MAX_VALUE;
static int distance(int sx,int sy,int dx,int dy)
{
return Math.abs(sx-dx)+Math.abs(sy-dy);
}
static void calCulateUtil(int mat[][],int n,int sx,int sy,int dx,int dy,int dis,boolean visited[])
{
ans=Math.min(ans,distance(sx,sy,dx,dy)+dis);
for(int i=0;i<n;i++)
{
if(visited[i]==false)
{
visited[i]=true;
int temp=distance(sx,sy,mat[i][0],mat[i][1])+dis+mat[i][4];
calCulateUtil(mat,n,mat[i][2],mat[i][3],dx,dy,temp,visited);
temp=distance(sx,sy,mat[i][2],mat[i][3])+dis+mat[i][4];
calCulateUtil(mat,n,mat[i][0],mat[i][1],dx,dy,temp,visited);
visited[i]=false;
}
}
}
static int calCulate(int mat[][],int n,int sx,int sy,int dx,int dy,boolean visited[])
{
calCulateUtil(mat,n,sx,sy,dx,dy,0,visited);
return ans;
}
public static void main (String[] args) {
Scanner sc=new Scanner(System.in);
int t=sc.nextInt();
while(t-->0)
{
int n=sc.nextInt();
int sx=sc.nextInt();
int sy=sc.nextInt();
int dx=sc.nextInt();
int dy=sc.nextInt();
int mat[][]=new int[n][5];
boolean visited[]=new boolean[n];
for(int i=0;i<n;i++)
{
for(int j=0;j<5;j++)
{
mat[i][j]=sc.nextInt();
}
}
System.out.println(calCulate(mat,n,sx,sy,dx,dy,visited));
}
}
}
