题意

给定$n$个城市，用$1~n$表示。有$3$辆车，开始都在点$1$上，要用这些车把杂志运送到各个城市里，当一个车在转移时，其他两辆车静止，并且两辆车不能跑到同一个位置，分配还得遵循递增的顺序，即城市$i$有了杂志后，车才能开到$i+1$城市送杂志。要求所有城市都送到杂志，汽车做过的路程和花费最小。

思路

动态规划。$dp[i][j][k]$分别表示$3$辆车所在城市$i,j,k$时所花费的最小时间。因为城市要按照城市标号递增的顺序送，所以可以反过来求，$dp[i][j][k+1]$表示$dp[i][j][k]$状态，k位置的车开到了k+1位置，其他同理。$dp[i][j][k] = min(dp[i][j][k+1] + dist[k][k+1], dp[j][k][k+1] + dist[i][k+1], dp[i][k][k+1] + dist[j][k+1]); 1<=i,j <=k。$

标程

#include <stdio.h>
#include <string.h>

#define min(a, b) ((a) < (b) ? (a) : (b))
#define N 35

int dp[N][N][N], dis[N][N];
int n, T;

int main() {
    scanf("%d", &T);
    while (T--) {
        int i, j, k;
        memset(dp, 0, sizeof(dp));
        memset(dis, 0, sizeof(dis));
        scanf("%d", &n);
        for (i = 1; i < n; i++) {
            for (j = i + 1; j <= n; j++) {
                scanf("%d", &dis[i][j]);
            }
        }
        for (k = n - 1; k >= 1; k--) {
            for (i = 1; i <= n; i++) {
                for (j = 1; j <= n; j++) {
                    dp[i][j][k] = min(dp[i][j][k + 1] + dis[k][k + 1], 
                                    min(dp[i][k][k + 1] + dis[j][k + 1],
                                        dp[j][k][k + 1] + dis[i][k + 1]));
                }
            }
        }
        printf("%d\n", dp[1][1][1]);
    }
    return 0;
}