dfs + 二分

90pts 是我用 mt19937 套数据乱搞的（（

#include "bits/stdc++.h"
using namespace std;

const int mod = 998244353, g = 3, invg = 332748118;

int f[1919][810], n;

int dfs(int hp, int t) {
	if (hp <= 0) return 0;
	if (t == n) return 1;
	int flg = 0;
	for (int i = 1; i <= n; ++i) {
		if (f[t][i] != 0) {
			flg |= dfs(hp * 2 + f[t][i], i);
		}
	}
	return flg;
}

	int search(int l, int r) {
		int mid;
		while (l < r) {
            
			mid = (l + r) / 2;
            // cout<<l<<' '<<r<<' '<<mid<<endl;
			if (dfs(mid, 1)) {
				r = mid;
			} else {
				l = mid + 1;
			}
		}
		return l;
	}

int main() {
    scanf ("%d", &n);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            scanf ("%d", &f[i][j]);
        }
    }
    printf ("%d", search(1, 35000));
}