Description

「飞奔」快递公司成立之后, 已经分别与市内许多中小企业公司签订邮件收送服务契约. 由于有些公司是在同一栋大楼内, 所以「飞奔」公司收件的地点 (收件点) 最多只有 \(m\) 点 \((1, 2, \ldots, m)\), 因此「飞奔」仅先行采购了三辆货車并聘用了三名司机, 每天早上分别从收件地点 \(1, 2\) 及 \(3\) 出发. 而在与客户的服务契约中有明确订约: 「飞奔」必须在客户提出邮件寄送要求的隔天派人至该公司 (地点) 收件.

为了能更有效率的服务客户并节省收件时间, 该公司设立了收件服务登记网站, 客户如有邮件需要寄送, 必须在需要收件的前一天就先上网登记. 为了节省油量, 「飞奔」就利用晚上先行安排三位司机隔天的收件路线. 每位司机至各地点收件的顺序应与各公司上网登记的顺序相符且必须能在最省油的情况下完成当天所有的收件服务. 因此每位司机有可能需要在不同时间重复到同一地点收件, 或不同的司机有可能需在不同的时间点前往同一地点收件.

如下面范例二: 收件公司地点依序为:\(4, 2, 4, 1, 5, 4, 3, 2, 1\) 所示, 虽然司机 \(1\) 一开始就已经在收件地点 \(1\) 了, 但是他却不能先把后面第四个登记的公司 (地点 \(1\)) 邮件先收了再前往第一、第二、或第三个登记收件地点 (地点 \(4, 2, 4\)) 收件. 但是如果前三个登记收件的服务是由司机 \(2\) 或 \(3\) 來负责, 则司机 \(1\) 就可以在地点 \(1\) 收了第四个登记的邮件后再前往后面所登记的地点收件.

此外, 在某些情况下, 不一定每辆车都要收到货, 也就是說, 最佳收件方式也有可能是只需出动一或兩辆车去收货. 请写一个程序來帮「飞奔」公司计算每天依预约顺序至各收件地点收件的最少总耗油量.

Input

输入文件第一行有一个整数 \(m (3 \leq m \leq 200)\), 代表「飞奔」公司收件的地点数, 以 \(1\) 至 \(m\) 之间的整数代号來表示每个地点.

接下來的 \(m\) 行 (第 \(2\) 到第 \(m+1\) 行), 每行有 \(m\) 个整数, 代表一个矩阵 \(D\). 第 \(i +1\) 行的第 \(j\) 个整数是 \(D(i, j)\),\(D(i, j)\) 代表司机开车从收件点 \(i\) 到收件点 \(j\) 所需耗油量.

最后有一行数串, 数串之数字依序为前一天上网登记要求收件的公司地点代号, 最多会有 \(1000\) 个收件请求. 输入文件中任兩个相邻的整数都以一个空白隔开.

Output

输出一个整数, 代表收件所需最少总耗油量.

Sample Input

4
0 5 0 6
6 0 5 6
1 6 0 6
1 1 1 0
1 1 1 1 4 4 2 2 2 3

Sample Output

6

Explanation

题目本身就是一个疯狂降维的过程......

记 \(f[l][i][j][k]\) 为在序列第 \(l\) 次, 三个司机分别在 \(i, j, k\) 的位置时的耗油量.

我们发现 \(i, j, k\) 的次序无关紧要, 所以可以瞎转移. 进一步地, 我们发现在三个位置中, 总有一个为收件序列的第 \(l\) 项, 于是这一维度可以省去.

状态转移允许滚动数组, 在使用一些奇怪的卡常技巧以后就可以水过了.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

#define rep(_var,_begin,_end) for(int _var=_begin;_var<=_end;_var++)
using namespace std;
typedef long long lli;
const int maxn = 1010;
const int infinit = 0x3f3f3f3f;

int n, m;
int dist[maxn][maxn];
int to[maxn];
int dp_arr[2][maxn][maxn];

int main(int argc, char** argv)
{
    scanf("%d", &n);
    rep(i, 1, n) rep(j, 1, n)
        scanf("%d", &dist[i][j]);
    // You might be using a fake stdin
    while (scanf("%d", &to[++m]) != EOF);
    // Rolling array
    int dp_pos = 0;
    #define dp_now dp_arr[dp_pos]
    #define dp_las dp_arr[!dp_pos]
    rep(k, 0, 1) rep(i, 0, n) rep(j, 0, n)
        dp_arr[k][i][j] = infinit;
    // Setting initial values
    dp_now[1][2] = dist[3][to[1]];
    dp_now[1][3] = dist[2][to[1]];
    dp_now[2][3] = dist[1][to[1]];
    // Dynamic programming
    rep(i, 2, m - 1) {
        dp_pos ^= 1;
        rep(j, 0, n) rep(k, 0, n)
            dp_now[j][k] = infinit;
        // Cleared.
        rep(j, 1, n) rep(k, j, n) {
            #define minimize(__x,__y,__z) dp_now[__x][__y]=dp_now[__y][__x]=min(dp_now[__x][__y],__z);
            minimize(j, k, dp_las[j][k] + dist[to[i-1]][to[i]]);
            minimize(to[i-1], k, dp_las[j][k] + dist[j][to[i]]);
            minimize(to[i-1], j, dp_las[j][k] + dist[k][to[i]]);
        }
    }
    // Getting minimum result
    int res = infinit;
    rep(i, 1, n) rep(j, i, n)
        res = min(res, dp_now[i][j]);
    printf("%d\n", res);
    return 0;
}