百度地图的实时路况 2016 计蒜之道 复赛
https://nanti.jisuanke.com/t/A1108
way1:
应该很多同学的做法都是对于每次y，每次x，dijkstra+堆优化
n^2 * nlogn
其实log(300)很小。。。
way2:
题解方法真心优秀！！！
cdq分治
有助于理解floyd：每次加入一个可以使用的点，加n次，顺序可以调整
本题：对于每个y，仅仅是y点不能使用
每次计算1/2，cdq剩下的1/2(left,right分别来一次)，直到只剩下一个数，这个点不用于求最短路。所有点都有且仅有一次出现“只剩下该点”的情况。
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cmath> 4 #include <cstring> 5 #include <string> 6 #include <algorithm> 7 #include <iostream> 8 using namespace std; 9 #define ll long long 10 11 const double eps=1e-8; 12 const int inf=1e9; 13 const ll mod=1e9+7; 14 const int maxn=3e2+10; 15 16 int dist[maxn][maxn]; 17 ll sum; 18 int n; 19 20 void cdq(int l,int r) 21 { 22 int i,j; 23 if (l==r) 24 { 25 for (i=1;i<=n;i++) 26 for (j=1;j<=n;j++) 27 if (i!=l && j!=l) 28 sum+=dist[i][j]==inf?-1:dist[i][j]; 29 return; 30 } 31 int m=(l+r)>>1,k,temp[maxn][maxn]; 32 memcpy(temp,dist,sizeof(dist)); 33 for (k=l;k<=m;k++) 34 for (i=1;i<=n;i++) 35 for (j=1;j<=n;j++) 36 if (dist[i][j]>dist[i][k]+dist[k][j]) 37 dist[i][j]=dist[i][k]+dist[k][j]; 38 cdq(m+1,r); 39 40 memcpy(dist,temp,sizeof(temp)); 41 for (k=m+1;k<=r;k++) 42 for (i=1;i<=n;i++) 43 for (j=1;j<=n;j++) 44 if (dist[i][j]>dist[i][k]+dist[k][j]) 45 dist[i][j]=dist[i][k]+dist[k][j]; 46 cdq(l,m); 47 } 48 49 int main() 50 { 51 int i,j; 52 scanf("%d",&n); 53 for (i=1;i<=n;i++) 54 for (j=1;j<=n;j++) 55 { 56 scanf("%d",&dist[i][j]); 57 if (dist[i][j]==-1) 58 dist[i][j]=inf; 59 } 60 cdq(1,n); 61 printf("%lld",sum); 62 return 0; 63 }