#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <random>
#include <chrono>
using namespace std;

random_device device;
mt19937 generator(device());
int **distances_matrix;
int **flows_matrix;


int foo(vector<int> ans) {
	int global_summ = 0;
	for (int i = 0; i < ans.size(); i++) {
		int plant_1 = ans[i];
		for (int j = i + 1; j < ans.size(); j++) {
			int plant_2 = ans[j];
			global_summ += distances_matrix[i][j] * flows_matrix[plant_1][plant_2];
		}
	}
	return global_summ;
}

vector<int> start_solution(int count_) {
	vector<int> ans;
	for (int i = 0; i < count_; i++) {
		ans.push_back(i);
	}
	uniform_int_distribution<int> distribution(0, ans.size() - 1);
	for (int i = 0; i < (count_ * 100); i++)
		swap(ans[distribution(generator)], ans[ans.size() - distribution(generator) - 1]);
	return ans;
}

vector<int> solution_swap(vector<int> ans) {
	uniform_int_distribution<int> distribution(0, ans.size() - 1);
	int position = distribution(generator);
	int direction = distribution(generator) % 2;
	if (direction) {
		swap(ans[position], ans[(position + 1) % (ans.size() - 1)]);
	}
	else if (position == 0) {
		swap(ans[position], ans[ans.size() - 1]);
	}
	else {
		swap(ans[position], ans[(position - 1)]);
	}
	return ans;
}

vector<int> compare(vector<int> ans_) {
	vector<int> best = ans_;
	int iter = 1000000;
	while (iter) {
		ans_ = solution_swap(ans_);
		if (foo(best) > foo(ans_))
			best = ans_;
		iter--;
	}
	return best;
}

//сам поиск(функцию, которая будет брать решение, делать из него соседа и сравнивать их)







int main() {
	string file_name = "C:/Users/Mike/Documents/Visual Studio 2017/projects/tai20a";
	ifstream file(file_name);
	int count;
	file >> count;
	distances_matrix = new int*[count];
	flows_matrix = new int*[count];
	for (int i = 0; i < count; i++) {
		distances_matrix[i] = new int[count];
		for (int j = 0; j < count; j++) {
			file >> distances_matrix[i][j];
		}
	}
	for (int i = 0; i < count; i++) {
		flows_matrix[i] = new int[count];
		for (int j = 0; j < count; j++) {
			file >> flows_matrix[i][j];
		}
	}
	vector<int> start = start_solution(count);
	vector<int> ans = compare(start);
	cout << foo(ans)<<" "<<foo(start);
	system("pause");
	return 0;
}