DISNEY1 - Công viên Disneyland (version 1)
Tác giả: ll931110
Ngôn ngữ: C++
//#pragma comment(linker, "/STACK:16777216")
#include <algorithm>
#include <bitset>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <deque>
#include <fstream>
#include <functional>
#include <iostream>
#include <map>
#include <set>
#include <sstream>
#include <stack>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
int f[205][205],L[205][205],n;
int main()
{
// freopen("disney1.in","r",stdin);
// freopen("disney1.ou","w",stdout);
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) scanf("%d", &L[i][j]);
for (int j = 2; j <= n; j++)
for (int i = 1; i <= j; i++)
for (int k = i + 1; k < j; k++) L[i][j] = min(L[i][j],L[i][k] + L[k][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++) f[i][j] = 1 << 29;
f[1][1] = 0;
for (int i = n - 1; i; i--) L[i][1] = min(L[i][1],L[i][i + 1] + L[i + 1][1]);
for (int j = 1; j < n; j++)
for (int i = 1; i <= j; i++)
{
f[j][j + 1] = min(f[j][j + 1],f[i][j] + L[i][j + 1]);
f[i][j + 1] = min(f[i][j + 1],f[i][j] + L[j][j + 1]);
}
int ret = 1 << 29;
for (int i = 1; i <= n; i++) ret = min(ret,f[i][n] + L[i][1] + L[n][1]);
printf("%d\n", ret);
}