百度地图的实时路况

百度地图的实时路况

https://nanti.jisuanke.com/t/11217

 

题意：d(u,v,w)：从u到w，严格不经过v的路径长度，计算每个d(u,v,w)，求和，n 300

分析：

　　floyed：去掉一个点直接最短路，复杂度$n^4$

　　优化：去掉一个点，重新做一遍floyed，太浪费了，发现去掉的两个点，除了这两个点不同，其他的中间点都一样。

　　于是，于是考虑solve(l,r)为l-r的点去掉的floyed矩阵。 二分mid，solve(l,mid)，此时先用mid+1~r作为中间点更新了矩阵。然后递归下去处理solve(l,mid)，当l=r说明当前的矩阵是去掉了l这个点的矩阵，然后就统计答案。 复杂度$n^3logn$

　　CDQ分治。

 

代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<iostream>
#include<cctype>
#include<set>
#include<vector>
#include<queue>
#include<map>
using namespace std;
typedef long long LL;

inline int read() {
    int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
}

const int N = 305;
const int INF = 1e9;
int dis[25][N][N];
int n;
LL Answer;

void update(int dep,int L,int R) {
    for (int i=1; i<=n; ++i) 
        for (int j=1; j<=n; ++j) 
            dis[dep][i][j] = dis[dep - 1][i][j];
    for (int k=L; k<=R; ++k) 
        for (int i=1; i<=n; ++i) 
            for (int j=1; j<=n; ++j) 
                dis[dep][i][j] = min(dis[dep][i][j], dis[dep][i][k] + dis[dep][k][j]);
}

void CDQ(int dep,int L,int R) {
    if (L > R) return ;
    if (L == R) {
        for (int i=1; i<=n; ++i) 
            for (int j=1; j<=n; ++j) 
                if (i != L && j != L) Answer += dis[dep][i][j] == INF ? -1 : dis[dep][i][j];
        return ;
    }
    int mid = (L + R) >> 1;
    update(dep + 1, mid + 1, R); CDQ(dep + 1, L, mid);
    update(dep + 1, L, mid); CDQ(dep + 1, mid + 1, R);
}
int main() {
    n = read();
    for (int i=1; i<=n; ++i) {
        for (int j=1; j<=n; ++j) {
            dis[0][i][j] = read();
            if (dis[0][i][j] == -1) dis[0][i][j] = INF;
        }
    }
    CDQ(0, 1, n);
    cout << Answer;
    return 0;
}