DISNEY1 - Công viên Disneyland (version 1)
Tác giả: happyboy99x
Ngôn ngữ: C++
#include<algorithm>
#include<iostream>
#include<cstring>
using namespace std;
const int N = 200, INF = 1e9;
int d[N][N], f[N][N], n;
template<class T> void checkMin(T &a, const T &b) {
if(b < a) a = b;
}
int main() {
ios::sync_with_stdio(false);
cin >> n;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j)
cin >> d[i][j];
memset(f, 0x3f, sizeof f);
int res = INF;
f[0][0] = 0;
for(int i = 0; i < n; ++i)
for(int j = 0; j < n; ++j) if(f[i][j] < INF) {
int next = max(i, j) + 1;
if(next == n) checkMin(res, f[i][j] + d[i][0] + d[j][0]);
else {
checkMin(f[i][next], f[i][j] + d[j][next]);
checkMin(f[next][j], f[i][j] + d[i][next]);
checkMin(f[next][next], f[i][j] + d[i][next] + d[j][next]);
}
}
cout << res << endl;
return 0;
}