Think.txt

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;

void fast();

bool compare(pair<long long, deque<int>>& p1, pair<long long, deque<int>>& p2);
pair<long long, deque<int>> get_min_path(int i, int j, vector<vector<long long>>& matrix, vector<vector<pair<long long, deque<int>>>>& memo, int& m, int& n);


int main() {

	fast();

	int m, n;

	while (cin >> m >> n) {

		vector<vector<long long>>matrix(m, vector<long long>(n)); 
		vector<vector<pair<long long, deque<int>>>>memo(m, vector<pair<long long, deque<int>>>(n + 1, { LLONG_MAX, {} }));
		vector<pair<long long, deque<int>>>paths(m);
		for (int i = 0; i < m; i++) {
			memo[i][n].first = 0;
		}
		for (int i = 0; i < m; i++) {
			for (int j = 0; j < n; j++)cin >> matrix[i][j];
		}
		for (int i = 0; i < m; i++) {
			paths[i] = get_min_path(i, 0, matrix, memo, m, n);
		}
		sort(paths.begin(), paths.end(), compare);
		for (int i = 0; i < paths[0].second.size(); i++) {
			cout << paths[0].second[i] + 1 << ' ';
		}
		cout << '\n';
		cout << paths[0].first << '\n';
		
	}
}

void fast() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	freopen("test.txt", "r", stdin);
}

pair<long long, deque<int>> get_min_path(int i, int j, vector<vector<long long>>& matrix, vector<vector<pair<long long, deque<int>>>>& memo, int& m, int& n) {

	pair<long long, deque<int>> paths[3];

	if (memo[(i + m - 1) % m][j + 1].first != LLONG_MAX) {
		paths[0].first = matrix[i][j] + memo[(i + m - 1) % m][j + 1].first;
		paths[0].second.push_back(i);
		for (int cnt = 0; cnt < memo[(i + m - 1) % m][j + 1].second.size(); cnt++) {
			paths[0].second.push_back(memo[(i + m - 1) % m][j + 1].second[cnt]);
		}
	}
	else {
		paths[0] = get_min_path((i + m - 1) % m, j + 1, matrix, memo, m, n);
		paths[0].first += matrix[i][j];
		paths[0].second.push_front(i);
	}

	if (memo[i][j + 1].first != LLONG_MAX) {
		paths[1].first = matrix[i][j] + memo[i][j + 1].first;
		paths[1].second.push_back(i);
		for (int cnt = 0; cnt < memo[i][j + 1].second.size(); cnt++) {
			paths[1].second.push_back(memo[i][j + 1].second[cnt]);
		}
	}
	else {
		paths[1] = get_min_path(i, j + 1, matrix, memo, m, n);
		paths[1].first += matrix[i][j];
		paths[1].second.push_front(i);
	}

	if (memo[(i + 1) % m][j + 1].first != LLONG_MAX) {
		paths[2].first = matrix[i][j] + memo[(i + 1) % m][j + 1].first;
		paths[2].second.push_back(i);
		for (int cnt = 0; cnt < memo[(i + 1) % m][j + 1].second.size(); cnt++) {
			paths[2].second.push_back(memo[(i + 1) % m][j + 1].second[cnt]);
		}
	}
	else {
		paths[2] = get_min_path((i + 1) % m, j + 1, matrix, memo, m, n);
		paths[2].first += matrix[i][j];
		paths[2].second.push_front(i);
	}

	sort(paths, paths + 3, compare);

	if (memo[i][j].first == LLONG_MAX) {
		memo[i][j].first = paths[0].first;
		for (int cnt = 0; cnt < paths[0].second.size(); cnt++) {
			memo[i][j].second.push_back(paths[0].second[cnt]);
		}
	}

	return paths[0];

}

bool compare(pair<long long, deque<int>>& p1, pair<long long, deque<int>>& p2) {
	if (p1.first < p2.first)return 1;
	else if (p1.first > p2.first)return 0;
	else {
		for (int i = 0; i < p1.second.size(); i++) {
			if (p1.second[i] < p2.second[i])return 1;
			else if (p1.second[i] > p2.second[i])return 0;
		}
		return 0;
	}
}