Description
Solution
设 (solve(l,r)) 为不经过 ([l,r]) 之间的点的最短路
考虑 (floyd) 需要枚举一个 (k) 作为中转站,我们只需要保证 (k) 不是 ([l,r]) 之间的就可以了
具体的我们用 ([l,mid]) 更新完之后去处理 (solve(mid+1,r)),用 ([mid+1,r]) 更新完之后去处理 (solve(l,mid)),就可以答案这个效果了
#include<bits/stdc++.h>
using namespace std;
const int N=305,inf=707406378;
int n,dis[10][N][N];long long ans=0;
inline void solve(int l,int r,int t){
if(l==r){
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i!=j && i!=l && j!=l)
ans+=(dis[t][i][j]>=inf?-1:dis[t][i][j]);
return ;
}
memset(dis[t+1],127/3,sizeof(dis[t+1]));
int mid=(l+r)>>1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[t+1][i][j]=dis[t][i][j];
for(int k=l;k<=mid;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[t+1][i][j]=min(dis[t+1][i][j],dis[t+1][i][k]+dis[t+1][k][j]);
solve(mid+1,r,t+1);
memset(dis[t+1],127/3,sizeof(dis[t+1]));
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[t+1][i][j]=dis[t][i][j];
for(int k=mid+1;k<=r;k++)
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
dis[t+1][i][j]=min(dis[t+1][i][j],dis[t+1][i][k]+dis[t+1][k][j]);
solve(l,mid,t+1);
}
int main(){
freopen("pp.in","r",stdin);
freopen("pp.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&dis[0][i][j]);
if(dis[0][i][j]==-1)dis[0][i][j]=inf;
}
solve(1,n,0);
cout<<ans<<endl;
return 0;
}