Tendency to think about problems
The problem seems complicated, but you can think about the principle of Floyd
It enumerates the intermediate points, and then compares them pairwise to find the shortest one
And this problem can be seen as an empty graph with one point added at a time
Then treat that point as the intermediate point and do Floyd
So Floyd only needs to be done once to solve it
// ############# ## ##### ## ############
// #### #### ## ####### ### #### ####
// ## ##### ## ## ## ### #### ### ###### ##
// ## ###### ## #### ######## ### ###### ##
// ## ###### ## ## #### ## ### ###### ##
// ## ## ## ######### ## ### ###
// ############# ## ## ## ## ## ##############
// ####### ####
// ### ## ########## ## ## #### ######
// ################# ## ######## ###############
// ################ ############## ###### #
// ## ################## ######### ## #
// ## ############## #### ########## ####
// ############# ## ## ## ### ########
// ####### ###### #### ##### #####
// ########## ### ## #### ######### ##
// ###### ### ## ## ## ###
// ############# ######## ## # #### ###
// ## ## #### ## #### ## ##
// ## ###### ## ## ##### ############# ###
// ## ###### ## #### ### #### ########
// ## ##### ## ############# ### ### ####
// ############# ################# ####### #
// ############ ### ###### # ## #
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <climits>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <cctype>
#include <utility>
#include <ctime>
using namespace std;
#ifdef DEBUG
#define VAR(a,b) decltype(b) a=(b)
#define debug(...) printf("DEBUG: "),printf(\_\_VA\_ARGS\_\_)
#define gettime() end\_time=clock();printf("now running time is %.7f\\n",(float)(end\_time - start\_time)/CLOCKS\_PER\_SEC);
#else
#define VAR(a,b) \_\_typeof(b) a=(b)
#define debug(...)
#define gettime()
#endif
typedef unsigned int uint;
typedef long long int Int;
typedef unsigned long long int UInt;
#define Set(a,s) memset(a,s,sizeof(a))
#define Write(w) freopen(w,"w",stdout)
#define Read(r) freopen(r,"r",stdin)
#define Pln() printf("\\n")
#define I\_de(x,n)for(int i=0;i<n;i++)printf("%d ",x\[i\]);Pln()
#define De(x)printf(#x"%d\\n",x)
#define For(i,x)for(int i=0;i<x;i++)
#define CON(x,y) x##y
#define Pmz(dp,nx,ny)for(int hty=0;hty<ny;hty++){for(int htx=0;htx<nx;htx++){\\
printf("%d ",dp\[htx\]\[hty\]);}Pln();}
#define M 505
#define PII pair<int,int\>
#define PB push\_back
#define oo INT\_MAX
#define Set\_oo 0x3f
#define FOR(a,b) for(VAR(a,(b).begin());a!=(b).end();++a)
#define eps 1e-6
#define X first
#define Y second
clock\_t start\_time=clock(), end\_time;
bool xdy(double x,double y){return x>y+eps;}
bool xddy(double x,double y){return x>y-eps;}
bool xcy(double x,double y){return x<y-eps;}
bool xcdy(double x,double y){return x<y+eps;}
int min3(int x,int y,int z){
int tmp=min(x,y);
return min(tmp,z);
}
int max3(int x,int y,int z){
int tmp=max(x,y);
return max(tmp,z);
}
int n;
Int mz\[M\]\[M\];
int del\[M\];
Int ans\[M\];
int vis\[M\];
int main() {
ios\_base::sync\_with\_stdio(0);
while(~scanf("%d",&n)){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++)scanf("%I64d",&mz\[i\]\[j\]);
}
for(int i=1;i<=n;i++)scanf("%d",&del\[i\]);
for(int k=n;k>=1;k--){
vis\[del\[k\]\]=1;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mz\[i\]\[j\]=min(mz\[i\]\[j\],mz\[i\]\[del\[k\]\]+mz\[del\[k\]\]\[j\]);
}
}
Int dis=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!vis\[i\]||!vis\[j\])continue;
dis+=mz\[i\]\[j\];
}
}
ans\[k\]=dis;
}
for(int i=1;i<=n;i++)printf("%I64d ",ans\[i\]);
Pln();
}
}