DISNEY2 - Công viên Disneyland (version 2)
Tác giả: ladpro98
Ngôn ngữ: C++
#include <bits/stdc++.h>
const int N = 222;
const int oo = 1000000009;
using namespace std;
int a[N][N], F[N][N], n;
int main()
{
//freopen("DISNEY1.in", "r", stdin);
scanf("%d\n", &n);
int i, j, k;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
scanf("%d", &a[i][j]);
n++;
for(j=1; j<=n; j++)
a[n][j] = a[j][n] = a[1][j];
for(i=1; i<=n; i++)
for(j=1; j<=n; j++)
F[i][j] = oo;
F[1][1] = 0;
for(i=1; i<=n; i++)
for(j=1; j<=n; j++) {
k = max(i, j) + 1;
F[k][j] = min(F[k][j], F[i][j] + a[i][k]);
F[i][k] = min(F[i][k], F[i][j] + a[j][k]);
if (k == n)
F[k][k] = min(F[k][k], F[i][j] + a[i][k] + a[j][k]);
}
printf("%d", F[n][n]);
return 0;
}