import java.util.Arrays;

 class TransportationProblem {
    private static final double INFINITY = Double.MAX_VALUE;
    
    public static void main(String[] args) {
        // Problem data
        String[] canneries = {"Bellingham", "Eugene", "Albert_Lea"};
        String[] warehouses = {"Sacramento", "Salt_Lake", "Rapid_City", "Albuquerque"};
        
        int[] supply = {75, 125, 100};
        int[] demand = {80, 65, 70, 85};
        
        double[][] cost = {
            {464, 513, 654, 867},
            {352, 416, 690, 791},
            {995, 682, 388, 685}
        };
        
        // Solve using Vogel's approximation method
        double[][] solution = solveTransportation(supply, demand, cost);
        
        // Print solution
        printSolution(canneries, warehouses, solution, cost);
    }
    
    public static double[][] solveTransportation(int[] supply, int[] demand, double[][] cost) {
        int m = supply.length;
        int n = demand.length;
        double[][] solution = new double[m][n];
        int[] s = Arrays.copyOf(supply, m);
        int[] d = Arrays.copyOf(demand, n);
        
        while (true) {
            // Find the cell with minimal cost in row or column with max penalty
            int[] cell = findNextCell(cost, s, d);
            if (cell == null) break;
            
            int i = cell[0], j = cell[1];
            double amount = Math.min(s[i], d[j]);
            solution[i][j] = amount;
            s[i] -= amount;
            d[j] -= amount;
            
            if (s[i] == 0) {
                for (int k = 0; k < n; k++) cost[i][k] = INFINITY;
            }
            if (d[j] == 0) {
                for (int k = 0; k < m; k++) cost[k][j] = INFINITY;
            }
        }
        
        return solution;
    }
    
    private static int[] findNextCell(double[][] cost, int[] s, int[] d) {
        // Simplified version of Vogel's approximation method
        double minCost = INFINITY;
        int[] cell = null;
        
        for (int i = 0; i < cost.length; i++) {
            if (s[i] == 0) continue;
            for (int j = 0; j < cost[0].length; j++) {
                if (d[j] == 0) continue;
                if (cost[i][j] < minCost) {
                    minCost = cost[i][j];
                    cell = new int[]{i, j};
                }
            }
        }
        
        return cell;
    }
    
    public static void printSolution(String[] sources, String[] destinations, 
                                   double[][] solution, double[][] cost) {
        System.out.println("Transportation Solution:");
        double totalCost = 0;
        
        for (int i = 0; i < solution.length; i++) {
            for (int j = 0; j < solution[0].length; j++) {
                if (solution[i][j] > 0) {
                    double costAmount = solution[i][j] * cost[i][j];
                    System.out.printf("%-10s → %-12s: %6.1f units (Cost: $%8.1f)%n",
                            sources[i], destinations[j], 
                            solution[i][j], costAmount);
                    totalCost += costAmount;
                }
            }
        }
        
        System.out.printf("%nTotal Transportation Cost: $%.1f%n", totalCost);
    }
}