AcWing 274. Mobile services [DP]

AcWing 274. Mobile services - AcWing

Put the stage on the outermost layer i enumeration , Don't care about the inner relationship . Because no aftereffect has been guaranteed by the outer stage .
secondly , For coordinates （x,y） still （y,x） Two for Loops can contain both , So no matter x On the outer layer or y It's the same in the outer layer , Because what you want to express is the form of coordinates , It doesn't matter who is on the outer layer , There must be .

For the first i Stage , There must be someone pi, We don't care who is pi, What I care about is except pi outside , Where are the other two positions .
So in the stage, set a two-dimensional array to record except pi Where are the other two positions .

The topological relationship between states here is quite special ,f[i][x][y] It's inconvenient to raise the dependent state , but f[i][x][y] The dependent ones are easy to enumerate

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N = 1100;
const int M = 220;
int c[N][N];
int n, m, res = 0x3f3f3f3f;
int p[N], f[N][M][M];
int main(){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    cin >> n >> m;
    for (int i = 1 ; i <= n; i ++ ) {
        for (int j = 1; j <= n; j ++ ) {
            cin >> c[i][j];
        }
    }   
    for (int i = 1; i <= m; i ++ ) {
        cin >> p[i];
    }
    p[0] = 3;
    memset(f, 0x3f, sizeof f);
    f[0][1][2] = 0;
    for (int i = 0; i < m; i ++ ) {
        for (int x = 1; x <= n; x ++ ) {
            for (int y = 1; y <= n; y ++ ) {
                int z = p[i], u = f[i][x][y];
                if(z == x || x == y || z == y)continue;
                int v = p[i + 1];
                f[i + 1][x][y] = min(f[i + 1][x][y], u + c[z][v]);//y、x You can change places 
                f[i + 1][z][x] = min(f[i + 1][z][x], u + c[y][v]);//z、x You can change places 
                f[i + 1][y][z] = min(f[i + 1][y][z], u + c[x][v]);
            }
        }
    }
    res = 0x3f3f3f3f;
    for (int x = 1; x <= n; x ++ ) {
        for (int y = 1; y <= n; y ++ ) {
            int z = p[m];
            if(z == x || x == y || y == z)continue;
            res = min(res, f[m][x][y]);
        }
    }
    cout << res << '\n';
    return 0;
}