putnik

#include <iostream>
#include <deque>
using namespace std;
int n, t[1500][1500], mn = 20000000;
deque<int> d(1, 0);
void h(int i, int cost) {
	if (i >= n) {
		mn = min(cost, mn);
		return;
	}
	if (cost > mn) return;
	int nc = cost+t[d.back()][i];
	d.push_back(i);
	h(i+1, nc);
	d.pop_back();
	nc = cost+t[d.front()][i];
	d.push_front(i);
	h(i+1, nc);
	d.pop_front();
}
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			cin >> t[i][j];
		}
	}
	h(1,0);
	cout << mn;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: TIME LIMIT EXCEEDED

Test 7

Verdict: TIME LIMIT EXCEEDED

Test 8

Verdict: TIME LIMIT EXCEEDED