用的dijkstra
做n遍最短路即可
时间复杂度 = O(m*(n(n-1)/2)logn) 实际上是远小于这个值的
理论最大值在4e7 ~ 1e8左右 但跑出来最长只有503ms
code:
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 110, M = 1e4 + 10;
int n, m;
struct node{
    int from, to, w;
    int ne;
}e[N * N];
int h[N], idx;
int des[M];
int ans;
typedef pair<int, int>pii;
int dist[N];
bool vis[N];

void add(int a, int b, int w){
    e[idx].to = b;
    e[idx].w = w;
    e[idx].ne = h[a];
    h[a] = idx++;
}

void jks(int st, int ed){
    memset(vis, 0, sizeof vis);
    memset(dist, 0x3f, sizeof dist);
    dist[st] = 0;

    priority_queue<pii, vector<pii>, greater<pii>>heap;
    heap.push({0, st});

    while(heap.size()){
        auto t = heap.top();
        heap.pop();
        int u = t.y;
        if(vis[u])continue;
        vis[u] = true;

        for(int i = h[u];~i;i = e[i].ne){
            int j = e[i].to;

            if(dist[j] > dist[u] + e[i].w){
                dist[j] = dist[u] + e[i].w;
                heap.push({dist[j], j});
            }
        }
    }
    ans += dist[ed];
    // cout << dist[ed] << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> m;
    memset(h, -1, sizeof h);
    for(int i = 1;i <= m;i++)cin >> des[i];

    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= n;j++){
            int w;
            cin >> w;
            if(i == j)continue;
            add(i, j, w);
        }
    }

    int st = 1;
    for(int i = 1;i <= m;i++){
        if(i == 1 && des[i] == 1 || des[i] == st){
            continue;
        }
        jks(st, des[i]);
        st = des[i];
        // cout << ans << endl;
    }

    cout << ans;

    return 0;
}