CapgeminiTechChallenge:Leve2(RoadConstruction)

RoadConstruction.java

/**
 * 
 *
 * @author VIK VIKKU VIKASHVVERMA
 * @website http://vikash-thiswillgoaway.blogspot.com
 */
public class RoadConstruction {

    public static int minimum_weight(String[] input1, int[] input2) {
        int ret = Integer.MAX_VALUE;
        int length = input1.length;

        int[][] cost = new int[length + 1][length + 1];
        int count = 0;
        int k = 0, l = 0;
        for (int i = 1; i <= length; i++) {
            for (int j = i + 1; j <= length; j++) {
                cost[j][i] = cost[i][j] = input2[count];
                count++;
                if (cost[i][j] < ret) {
                    k = i;
                    l = j;
                }
            }
        }

        
        ret=primMinimumSpanning(input1, cost, length, k, l);
        return ret;

    }

    static int primMinimumSpanning(String[] edge, int[][] cost, int n, int k, int l) {
        int mincost = 0;
        int[] near = new int[n + 1];
        
        for (int i = 2; i <= n; i++) 
            near[i]=1;
        near[1]=0;
        for (int i = 1; i < n; i++) {
        
        int j=getMinimum(cost, near, n);
        mincost=mincost+cost[j][near[j]];
        near[j]=0;
            for (int m = 1; m <=n; m++) {
                if(near[m]!=0 && cost[m][near[m]]>cost[m][j])
                {
                    near[m]=j;
                }
            }
        }

        return mincost;
    }

    static int getMinimum(int[][] cost,int[] near,int n) {
        int ret = -1;
        int min=Integer.MAX_VALUE;
        for (int i = 1; i <=n; i++) {
           if(near[i]!=0)
           {
               if(cost[i][near[i]]<min)
               {
                   min=cost[i][near[i]];
                   ret=i;
               }
           }
        }

        return ret;

    }

    
}