# Clear And Present Danger## 题面翻译农夫约翰正驾驶一条小艇在牛勒比海上航行．海上有 $N1leq Nleq 100$ 个岛屿用 $1$ 到 $N$ 编号．约翰从 $1$ 号小岛出发最后到达 $N$ 号小岛．一张藏宝图上说如果他的路程上经过的小岛依次出现了 $A_1A_2dots A_M2leq Mleq 10000$ 这样的序列不一定相邻那他最终就能找到古老的宝藏．

#include <iostream>
#include <cstdio>

using namespace std;

const int N = 100 + 7;
const int M = 1e4 + 7;

int n, m;
int a[M];
int g[N][N];
int f[N][M];

int main()
{
    scanf("%d %d", &n, &m);
    for(int i = 1; i <= m; i++)
        scanf("%d", &a[i]);
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            scanf("%d", &g[i][j]);
    for(int i = 0; i <= n; i++)
        for(int j = 1; j <= m; j++)
            f[i][j] = 0x3f3f3f3f;
    f[1][0] = 0;
    for(int i = 1; i <= m; i++)
        for(int j = 1; j <= n; j++)
            for(int k = 1; k <= n; k++)
                if(a[i] == j)
                    f[j][i] = min(f[j][i], f[k][i - 1] + g[k][j]);
                else
                    f[j][i] = min(f[j][i], f[k][i] + g[k][j]);
    printf("%d\n", f[n][m]);
    return 0;
}
``