import java.util.*;
import java.io.*;
import com.hexaly.optimizer.*;

public class OrderPicking {
    private int nbOrders;
    private int[][] distancesData;

    final HexalyOptimizer optimizer;
    private HxExpression pickingList;
    private HxExpression objective; 

    private HxExpression indexInitialPosition;

    private OrderPicking(HexalyOptimizer optimizer) {
        this.optimizer = optimizer;
    }

    private void readInstance(String inputFile) throws IOException {
        try (Scanner input = new Scanner(new File(inputFile))) {
            input.useLocale(Locale.ROOT);
            nbOrders = input.nextInt() + 1;
            distancesData = new int[nbOrders][nbOrders];
            for (int i = 0; i < nbOrders; ++i) {
                for (int j = 0; j < nbOrders; ++j) {
                    distancesData[i][j] = input.nextInt();
                }
            }
        }
    }

    public void solve(int timeLimit) {
        // Declare the model
        HxModel model = optimizer.getModel();

        // Declare the list containing the picking order
        pickingList = model.listVar(nbOrders);

        // All orders must be picked
        model.constraint(model.eq(model.count(pickingList), nbOrders));

        // Create a HexalyOptimizer array for the distance matrix in order to access it using the "at" operator
        HxExpression distancesMatrix = model.array(distancesData);

        // Lambda expression to compute the distance to the next order
        HxExpression distanceToNextOrderLambda = model.lambdaFunction( i -> 
            model.at(distancesMatrix, model.at(pickingList, i), model.at(pickingList, model.sum(i, 1))));

        // The objective is to minimize the total distance required to pick 
        // all the orders and to go back to the initial position
        objective = model.sum(model.sum(model.range(0, nbOrders - 1), distanceToNextOrderLambda),
            model.at(distancesMatrix, model.at(pickingList, nbOrders - 1), model.at(pickingList, 0)));

        // Store the index of the initial position in the list.
        // It will be used at the end to write the solution starting from the initial point.
        indexInitialPosition = model.indexOf(pickingList, 0);

        model.minimize(objective);

        // End of the model declaration
        model.close();

        optimizer.getParam().setTimeLimit(timeLimit);

        optimizer.solve();
    }

    public void writeSolution(String inputFile) throws IOException {
        try (PrintWriter output = new PrintWriter(inputFile)) {
            output.println(objective.getValue());
            HxCollection pickingListCollection = pickingList.getCollectionValue();
            for (int i = 0; i < nbOrders; ++i) {
                int index = ((int)indexInitialPosition.getValue() + i) % nbOrders;
                output.print(pickingListCollection.get(index) + " ");
            }
            output.println();
        }
    }

    public static void main(String[] args) {
        if (args.length < 1) {
            System.out.println("Usage: java OrderPicking inputFile [outputFile] [timeLimit]");
            System.exit(1);
        }

        String inputFile = args[0];
        String outputFile = args.length > 1 ? args[1] : null;
        String strTimeLimit = args.length > 2 ? args[2] : "10";

        try (HexalyOptimizer optimizer = new HexalyOptimizer()) {
            OrderPicking model = new OrderPicking(optimizer);
            model.readInstance(inputFile);
            model.solve(Integer.parseInt(strTimeLimit));
            if (outputFile != null) {
                model.writeSolution(outputFile);
            }
        } catch(Exception ex) {
            System.err.println(ex);
            ex.printStackTrace();
            System.exit(1);
        }
    }
}
