13211 Geonosis

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, g[505][505], ans = 0;
    cin >> n;
    vector<int> order(n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> g[i][j];
        }
    }
    for (int i = n - 1; i >= 0; i--) cin >> order[i];

    for (int i = 0; i < n; i++) {
        int it = order[i];
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                g[a][b] = min(g[a][b], g[a][it] + g[it][b]);
            }
        }
        for (int a = 0; a < i + 1; a++) {
            for (int b = 0; b < i + 1; b++) {
                if (a != b) ans += g[order[a]][order[b]];
            }
        }
    }
    cout << ans << '\n';
}

signed main() {
    int t;
    cin >> t;
    while (t--) solve();
}