|
|
思路：
一個 O(N^3) 的動態規劃，由于 N 比較小，所以沒啥問題。
f[i][j][k] = { 從一開始到三輛車分別位于 i, j, k 的時候，所有車走過的距離之和的最小值 }
其中 i <= j <= k
狀態轉移：
1. 第一輛車走到 k + 1
2. 第二輛車走到 k + 1
3. 第三輛車走到 k + 1
注意：
兩點之間的距離跟輸入一致。
不可以計算兩點間的最短距離，這樣會 WA。
這是題目沒有描述清楚！
 #include <stdio.h>
#define MAX_N 32
#define MAX_DIS 0x70000000
int M, N;
int D[MAX_N][MAX_N];
int dp[MAX_N][MAX_N][MAX_N];
inline void update(int *a, int b)
   {
 if (b < *a)
*a = b;
 }
int main()
{
int i, j, k, v;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d", &M);
  while (M--) {
scanf("%d", &N);
for (i = 1; i <= N - 1; i++) {
for (j = i + 1; j <= N; j++) {
scanf("%d", &v);
D[i][j] = D[j][i] = v;
 }
}
/**//*
兩點之間的距離跟輸入一致。
不可以計算兩點間的最短距離，這樣會 WA。
這是題目沒有描述清楚！
for (k = 1; k <= N; k++)
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
if (D[i][k] + D[k][j] < D[i][j])
D[i][j] = D[i][k] + D[k][j];
*/
for (i = 1; i <= N; i++)
for (j = 1; j <= N; j++)
for (k = 1; k <= N; k++)
dp[i][j][k] = MAX_DIS;
dp[1][1][1] = 0;
for (i = 1; i <= N - 1; i++) {
for (j = 1; j <= i; j++) {
for (k = j; k <= i; k++) {
update(&dp[k][i][i + 1], dp[j][k][i] + D[j][i + 1]);
update(&dp[j][i][i + 1], dp[j][k][i] + D[k][i + 1]);
update(&dp[j][k][i + 1], dp[j][k][i] + D[i][i + 1]);
}
}
}
v = MAX_DIS;
for (i = 1; i <= N; i++)
for (j = i; j <= N; j++)
update(&v, dp[i][j][N]);
printf("%d\n", v);
}
return 0;
}
|