#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define fx(x,a,b) for(int x=(a);x<=(b);x++)
#define fd(x,a,b) for(int x=(a);x>=(b);x--)
#define LL long long
using namespace std;
int f[1005][205][205],c[205][205],p[1005],l,n,T;
int main(){
cin>>T;
while(T--) {
cin>>l>>n;
fx(i,1,l) fx(j,1,l) cin>>c[i][j];
fx(i,1,n) cin>>p[i];
memset(f,0x3f,sizeof(f)); p[0]=3,f[0][1][2]=0;
fx(i,0,n-1){
fx(j,1,l){
fx(k,1,l){
if(j==p[i]||k==p[i]||j==k) continue;
if(j!=p[i+1]&&k!=p[i+1])
f[i+1][j][k]=min(f[i+1][j][k],f[i][j][k]+c[p[i]][p[i+1]]);
if(k!=p[i+1]&&p[i]!=p[i+1])
f[i+1][p[i]][k]=min(f[i+1][p[i]][k],f[i][j][k]+c[j][p[i+1]]);
if(j!=p[i+1]&&p[i]!=p[i+1])
f[i+1][j][p[i]]=min(f[i+1][j][p[i]],f[i][j][k]+c[k][p[i+1]]);
}
}
}
int ans=1e9;
fx(i,1,l) fx(j,1,l)
ans=min(ans,f[n][i][j]);
cout<<ans<<endl;
}
return 0;
}
全部评论
(1) 回帖