TopCoder SRM 170 Div1 - Level2

Problem Links:

http://community.topcoder.com/stat?c=problem_statement&pm=1864&rd=4655

Problem:

TopCoder SRM170 Div1 - Level II

Solution:

This problem demonstrates how we implement the solution with real understanding of the algorithm.

After reading the the problem, the time it asking is the distance between two cities, and we need to know the maximum distance between any two cities with the minimum cost. It's like Max(min1, min2, min3, ...)

When asking about distance between any two nodes, the first choice is always Floyd algorithm, which is a O(n^3) algorithm. But here, the way we calculate the distance needs our tention. When we were asking about the distance between two cities, it's not going be the sum of two distance, instead, it will be maximum of two costs.

---

Source Code:

import java.util.*;
import java.util.regex.*;
import java.text.*;
import java.math.*;
import java.awt.geom.*;

public class CityLink
{
 
 public int timeTaken(int[] x, int[] y)
 {
  int N = x.length;
  int[][] dist = new int[N][N];
  for(int i=0; i<N; i++) 
   for(int j=0; j<N; j++) 
    dist[i][j] = Integer.MAX_VALUE;
  for(int i=0; i<N; i++) 
   for(int j=0; j<N; j++) 
    dist[i][j] = distance(x[i], y[i], x[j], y[j]);
  
  
        // Floyd Graph Algorithms, calculate the minimum time(distance) between any two cities.
  for(int k=0; k<N; k++){
   for(int i=0; i<N; i++){
    //if(i==k)continue;
    for(int j=0; j<N; j++){
     //if(j==k || j==i) continue;
                    //Here is the key. To connect the two cities through one, this is how we calculate the cost(distance).
     dist[i][j] = Math.min(dist[i][j], Math.max(dist[i][k], dist[k][j]));
    }
   }
  }
  int max = 0;
  for(int i=0; i<N; i++) 
   for(int j=0; j<N; j++)
    max = Math.max(max, dist[i][j]);
  
  return max;
 }
 
 private int distance(int x1, int y1, int x2, int y2){
  if(x1 == x2) return (Math.abs(y1-y2)+1)/2;
  if(y1 == y2) return (Math.abs(x1-x2)+1)/2;
  return Math.max(Math.abs(x1-x2), Math.abs(y1-y2));
 }
}
//Powered by [KawigiEdit] 2.0!