2016计蒜之道复赛A 百度地图的实时路况-白红宇

2016计蒜之道复赛A 百度地图的实时路况

阅读量：4596 次

发布时间：2019-06-09

本文共 2839 字，大约阅读时间需要 9 分钟。

百度地图的实时路况功能相当强大，能方便出行的人们避开拥堵路段。一个地区的交通便捷程度就决定了该地区的拥堵情况。假设一个地区有

那么这个地区的交通便捷程度

$\sum_{1 \leq x,y,z \leq n , x \neq y , y \neq z}{d(x,y,z)}P=∑1≤x,y,z≤n,x≠y,y≠zd(x,y,z)$

现在我们知道了该地区的

输入格式

第一行输入一个正整数 $\leq n \leq 300)n(4≤n≤300)，表示该地区的点数。$

接下来输入 $Gi,j(−1≤Gi,j≤10000;Gi,i=0)G_{i,j}(-1 \leq G_{i,j} \leq 10000;G_{i,i} = 0)Gi,j(−1≤Gi,j≤10000;Gi,i=0) 表示从 iii 号点到 jjj 号的有向路径长度。如果这个数为 −1-1−1，则表示不存在从 iii 号点出发到 jjj 号点的路径。$

输出格式

输出一个整数，表示这个地区的交通便捷程度。

样例输入

40 1 -1 -1-1 0 1 -1-1 -1 0 11 -1 -1 0

样例输出

4 【题解】 “Floyd 算法又叫 “插点法” 注意到插点的顺序是无关紧要的 我们可以分治： 令 solve(l, r) 表示处理区间 [l, r] 的询问 取 mid = (l + r) / 2 把 [l, mid] 的点插入，递归 solve(mid + 1, r)； 把 [mid + 1, r] 的点插入，递归 solve(l, mid)； 递归到叶子的时候，回答询问 复杂度 O(N^3\log N)，只需注意到每个点会被插 O(\log N) 次” —— 吕欣

1 #include 
        
          2 #include 
         
           3 #include 
          
            4 #include 
           
             5 #include 
            
              6 #include 
             
               7 #define max(a, b) ((a) > (b) ? (a) : (b)) 8 #define min(a, b) ((a) < (b) ? (a) : (b)) 9 10 inline void read(int &x)11 {12 x = 0;char ch = getchar(), c = ch;13 while(ch < '0' || ch > '9')c = ch, ch = getchar();14 while(ch <= '9' && ch >= '0')x = x * 10 + ch - '0', ch = getchar();15 if(c == '-')x = -x;16 }17 18 const int INF = 0x3f3f3f3f;19 const int MAXN = 300 + 10;20 21 int g[MAXN][MAXN],n;22 long long ans;23 24 void solve(int l, int r)25 {26 if(l == r)27 {28 for(register int i = 1;i <= n;++ i)29 {30 if(l == i) continue;31 for(register int j = 1;j <= n;++ j)32 {33 if(r == j) continue;34 if(g[i][j] != INF)35 ans += g[i][j];36 else37 -- ans;38 }39 }40 return;41 }42 int tmp[MAXN][MAXN];43 for(register int i = 1;i <= n;++ i)44 for(register int j = 1;j <= n;++ j)45 tmp[i][j] = g[i][j];46 int mid = (l + r) >> 1;47 for(register int k = l;k <= mid;++ k)48 for(register int i = 1;i <= n;++ i)49 for(register int j = 1;j <= n;++ j)50 if(g[i][j] > g[i][k] + g[k][j])51 g[i][j] = g[i][k] + g[k][j];52 solve(mid + 1, r);53 for(register int i = 1;i <= n;++ i)54 for(register int j = 1;j <= n;++ j)55 g[i][j] = tmp[i][j];56 for(register int k = mid + 1;k <= r;++ k)57 for(register int i = 1;i <= n;++ i)58 for(register int j = 1;j <= n;++ j)59 if(g[i][j] > g[i][k] + g[k][j])60 g[i][j] = g[i][k] + g[k][j];61 solve(l, mid);62 return;63 }64 65 int main()66 {67 read(n);68 for(register int i = 1;i <= n;++ i)69 for(register int j = 1;j <= n;++ j)70 {71 read(g[i][j]);72 if(g[i][j] == -1)g[i][j] = INF;73 }74 solve(1, n);75 printf("%lld", ans);76 return 0;77 }

Code

转载于:https://www.cnblogs.com/huibixiaoxing/p/7560610.html

你可能感兴趣的文章

keep the bar green to keep the code clean——Junit详解（二）