算法

(DP,线性DP) $O(NL^2)$

状态表示：

• f[i][x][y]表示已经处理完前i个请求，且三个服务员分别在p[i], x, y的所有方案的集合；
• f[i][x][y]的值是集合中所有方案的花费的最小值；

状态计算：
这里状态之间的拓扑关系比较特殊，f[i][x][y]所依赖的状态枚举起来不太方便，但f[i][x][y]被依赖的很容易枚举，只有3类：

• 位于p[i]的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][y] = f[i][x][y] + w[p[i]][p[i + 1]];
• 位于x的服务员出发前往p[i + 1]，此时状态变成f[i + 1][p[i]][y] = f[i][x][y] + w[x][p[i + 1]];
• 位于y的服务员出发前往p[i + 1]，此时状态变成f[i + 1][x][p[i]] = f[i][x][y] + w[y][p[i + 1]];

最终答案从f[m][1...n][1...n]取最小值即可。

时间复杂度

共有 $NL^2$ 个状态，计算每个状态需要 $O(1)$ 的计算量，因此总时间复杂度是 $O(NL^2)$。

C++ 代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 210, M = 1010, INF = 0x3f3f3f3f;

int n, m;
int w[N][N];
int f[M][N][N];
int p[M];

int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
        for (int j = 1; j <= n; j ++ )
            scanf("%d", &w[i][j]);
    for (int i = 1; i <= m; i ++ ) scanf("%d", &p[i]);

    p[0] = 3;
    memset(f, 0x3f, sizeof f);
    f[0][1][2] = 0;
    for (int i = 0; i < m; i ++ )
        for (int x = 1; x <= n; x ++ )
            for (int y = 1; y <= n; y ++ )
            {
                int z = p[i], v = f[i][x][y];
                if (x == y || x == z || y == z) continue;
                int u = p[i + 1];
                f[i + 1][x][y] = min(f[i + 1][x][y], v + w[z][u]);
                f[i + 1][z][y] = min(f[i + 1][z][y], v + w[x][u]);
                f[i + 1][x][z] = min(f[i + 1][x][z], v + w[y][u]);
            }

    int res = INF;
    for (int x = 1; x <= n; x ++ )
        for (int y = 1; y <= n; y ++ )
        {
            int z = p[m];
            if (x == y || x == z || y == z) continue;
            res = min(res, f[m][x][y]);
        }

    printf("%d\n", res);

    return 0;
}