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; }

轉載于:https://www.cnblogs.com/Yuzao/p/8503925.html

總結

以上是生活随笔為你收集整理的计蒜客 百度地图的实时路况的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。