清河网站建设网络公司,哪个网站空间好,海外免费网站推广有哪些,网络营销推广的目标与策略loj2090. 「ZJOI2016」旅行者 链接 loj 思路 \((l,mid)(mid1,r)\).考虑跨过mid的贡献。 假设选的中间那条线的点为gzy,贡献为\(dis(x,gzy)dis(gzy,y)\) 那就计算n遍最短路,一次分治为\(n^2mlog{nm}\) 设Sn*m.矩阵的长度是不定的#xff0c;每次取最长的边进行分治是最好的1,r)\).考虑跨过mid的贡献。 假设选的中间那条线的点为gzy,贡献为\(dis(x,gzy)dis(gzy,y)\) 那就计算n遍最短路,一次分治为\(n^2mlog{nm}\) 设Sn*m.矩阵的长度是不定的每次取最长的边进行分治是最好的n最坏为\(\sqrt{n}\)。 \(f(n)2*f(\frac{n}{2})S\sqrt{S}logS。所以总的复杂度就是\)\(S\sqrt{S}logS\) 都在同侧的也需要跨一跨 代码 #include bits/stdc.h
#define FOR(i,a,b) for(int ia;ib;i)
using namespace std;
const int _1e57,INF0x3f3f3f3f;
int read() {int x0,f1;char sgetchar();for(;s9||s0;sgetchar()) if(s-) f-1;for(;s0s9;sgetchar()) xx*10s-0;return x*f;
}
int n,m,q,ans[_],vis[_];
struct node {int x,y,X,Y,u,v,id;
}Q[_],tmp[_];
bool cmp(node a,node b) {return a.idb.id;}
struct edge {int v,nxt,q;}e[_];
int head[_],tot;
void add(int u,int v,int q) {e[tot].vv;e[tot].qq;e[tot].nxthead[u];head[u]tot;
}
int id(int x,int y) {return (x-1)*my;}
struct T_T {int u,val;T_T(int a0,int b0) {ua,valb;}bool operator (const T_T b) const {return valb.val;}
};
int dis[_];
void dij(int S) {dis[S]0;priority_queueT_T q;q.push(T_T(S,0));while(!q.empty()) {T_T uq.top();q.pop();if(dis[u.u]!u.val) continue;for(int ihead[u.u];i;ie[i].nxt) {int ve[i].v;if(vis[v]dis[v]u.vale[i].q) {dis[v]u.vale[i].q;q.push(T_T(v,dis[v]));}}}
}
void solve(int x,int y,int X,int Y,int l,int r) {if(lr) return;if(xXyY) {for(int il;ir;i) ans[Q[i].id]0;return;}if(Y-yX-x) {int mid(Yy)1;FOR(i,x,X) {FOR(j,x,X) FOR(k,y,Y) dis[id(j,k)]INF;dij(id(i,mid));FOR(j,l,r)ans[Q[j].id]min(dis[Q[j].u]dis[Q[j].v],ans[Q[j].id]);}FOR(i,x,X) vis[id(i,mid)]0;int pl,qr;FOR(i,l,r) {if(max(Q[i].y,Q[i].Y)mid) tmp[p]Q[i];if(min(Q[i].y,Q[i].Y)mid) tmp[q--]Q[i];}FOR(i,l,r) Q[i]tmp[i];solve(x,y,X,mid,l,p-1);solve(x,mid1,X,Y,q1,r);} else {int mid(Xx)1;FOR(i,y,Y) {FOR(j,x,X) FOR(k,y,Y) dis[id(j,k)]INF;dij(id(mid,i));FOR(j,l,r)ans[Q[j].id]min(dis[Q[j].u]dis[Q[j].v],ans[Q[j].id]);}FOR(i,y,Y) vis[id(mid,i)]0;int pl,qr;FOR(i,l,r) {if(max(Q[i].x,Q[i].X)mid) tmp[p]Q[i];if(min(Q[i].x,Q[i].X)mid) tmp[q--]Q[i];}FOR(i,l,r) Q[i]tmp[i];solve(x,y,mid,Y,l,p-1);solve(mid1,y,X,Y,q1,r);}
}
int main() {nread(),mread();FOR(i,1,n) FOR(j,1,m-1) {int valread();add(id(i,j),id(i,j1),val);add(id(i,j1),id(i,j),val);}FOR(i,1,n-1) FOR(j,1,m) {int valread();add(id(i,j),id(i1,j),val);add(id(i1,j),id(i,j),val);}FOR(i,1,n) FOR(j,1,m) vis[id(i,j)]1;qread();FOR(i,1,q) {Q[i].xread(),Q[i].yread(),Q[i].uid(Q[i].x,Q[i].y);Q[i].Xread(),Q[i].Yread(),Q[i].vid(Q[i].X,Q[i].Y);Q[i].idi,ans[i]INF;}solve(1,1,n,m,1,q);FOR(i,1,q) printf(%d\n,ans[i]);return 0;
} 转载于:https://www.cnblogs.com/dsrdsr/p/11405996.html
