|
|
思路：
一个 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;
}
|