农夫寻宝

题目：https://www.luogu.com.cn/problem/P2910

题解

#include <stdio.h>

#define min(a, b) ({\
    (a) > (b) ? (b) : (a);\
})

const int MAX_N = 105;

/*
int head[MAX_N], nex[MAX_N], D[MAX_N], to[MAX_N], cnt_edge;
inline int add_edge(int a, int b, int d) {
    to[++cnt_edge] = b;
    D[cnt_edge] = d;
    nex[cnt_edge] = head[a];
    head[a] = cnt_edge;
    return 1;
}
*/
int to_next[10004];
int n, m;
long long d[101][101];

int main() {
    //输入数据 
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        scanf("%d", &to_next[i]);
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%lld", &d[i][j]);
        }
    }
    
    //  Floyd
    
    for (int k = 1; k <= n; k++) {
        for (int l = 1; l <= n; l++) {
            for (int r = 1; r <= n; r++) {
                d[l][r] = min(d[l][r], d[l][k] + d[k][r]);
            }
        }
    }
    long long ans = 0;
    for (int i = 2; i <= m; i++) {
        //printf("%lld\n", d[to_next[i - 1]][to_next[i]]); 
        ans += d[to_next[i - 1]][to_next[i]];
    }
    printf("%lld\n", ans);
    return 0;
}