●计蒜客 百度地图的实时路况
题链：
https://nanti.jisuanke.com/t/11217
题解：
分治，最短路。
如果我们规定只能经过编号为l~r的点，
那么Floyd就可以很好地计算出此情况下的任意两点间的最短路。
(只需让Floyd的第一层循环k从l枚举到r即可)
由于题目需要求不经过某一个点时的最短路径之和，
显然我们可以可以沿用上面的做法：假设此时不能经过p号点，
那么我们就让Floyd的第一层循环k从1枚举到p-1再从p+1枚举到N。
这样做的复杂度为O(N^4)。
但是注意到对于两种情况：不经过p1,不经过p2,(令p1<p2)
在分别做Floyd的时候，其实是有很多相同的部分：
(即Floyd的第一层循环都枚举了1~p1-1,p1+1~p2-1,p2+1~N)
所以由此收到启发，我们可以使用分治的方法来避免重复计算。
divide(l,r)表示不经过编号为l~r的点时的dis[][]数组，
显然由定义可知，1~l-1,r+1~N的点都可能作为中转点，即被Floyd的第一层循环枚举过。
最后到了divide(l,l)时，得到的dis[][]数组就是不经过l点时的任意两点间的最短路了。
复杂度O(N^3 logN)。
代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=305;
int N; ll ANS;
void Floyd(int l,int r,int dis[MAXN][MAXN]){
for(int k=l;k<=r;k++)
for(int i=1;i<=N;i++) if(i!=k&&dis[i][k]!=-1)
for(int j=1;j<=N;j++) if(j!=k&&dis[k][j]!=-1){
if(dis[i][j]==-1) dis[i][j]=dis[i][k]+dis[k][j];
else dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
}
void divide(int l,int r,int dis[MAXN][MAXN]){
if(l==r){
for(int i=1;i<=N;i++) if(i!=l)
for(int j=1;j<=N;j++) if(j!=l&&i!=j)
ANS+=dis[i][j];
return;
}
int mid=(l+r)>>1;
int (*disl)[MAXN]=new int[MAXN][MAXN];
memcpy(disl,dis,MAXN*MAXN*4);
Floyd(mid+1,r,disl);
divide(l,mid,disl);
delete []disl;
int (*disr)[MAXN]=new int[MAXN][MAXN];
memcpy(disr,dis,MAXN*MAXN*4);
Floyd(l,mid,disr);
divide(mid+1,r,disr);
delete []disr;
}
int main(){
scanf("%d",&N);
int (*dis)[MAXN]=new int[MAXN][MAXN];
for(int i=1;i<=N;i++)
for(int j=1;j<=N;j++)
scanf("%d",&dis[i][j]);
divide(1,N,dis);
printf("%lld
",ANS);
return 0;
}