题目大意
详细题目传送门
给一个 \(m\) 行 \(n\) 列的网格图，相邻格子之间有边权。 \(q\) 组询问求 \((a,b)\) 到 \((c,d)\) 的最短路。
\(m\leq10,n\leq10^5\)
思路
首先想利用网格图和这个 \(m=10\) 的条件，否则一定是朴素最短路没有优化空间的。注意到有 \(m=2\) 的部分分，联想到一道题堵塞的交通。这题是 \(m=2\) 的网格图维护连通性，做法是线段树。所以发现这个网格图应该也是满足分治可以用类似方法线段树维护的。
我们考虑维护列数，线段树 \([l,r]\) 维护第 \(l\) 列和第 \(r\) 列之间每一个 \((i,l)\) 到 \((j,r)\) 的最短路。所以我们希望维护一个 \(F(l,r,x,y)\) 表示 \((x,l)\) 到 \((y,r)\) 的最短路。发现如果考虑分治的话就可以：
\[F(l,r,x,y)=\min_k F(l,mid,x,k)+A_{k,mid}+F(mid+1,r,k,y) \]
其中 \(mid=\frac{l+r}{2}\)，\(A_{k,mid}\) 表示 \((k,mid)\) 到 \((k,mid+1)\) 的边权。
于是我们就可以维护出任意一个 \(F(l,r,x,y)\) 了。之后考虑维护 \(F(i,i,x,y)\)，即一列里面任意两点最短路。发现一定是在一列里面直接走或者从左边一列或右边一列加上列之间的边权的最小值。于是维护 \(L(i,x,y)\) 表示除了从 \((i,x)\) 出去和回到 \((i,y)\) 外其余的列数全部小于 \(i\) 的最短路。同理维护一个 \(R(i,x,y)\) 表示全部大于 \(i\) 的。
发现 \(L(i),R(i)\) 可以通过在 \(L(i-1),R(i+1)\) 的基础上新加上列之间的边权之后跑弗洛伊德得到。
之后再用 \(V(i)=\min(L(i),R(i))\) 再跑弗洛伊德。
最后时间复杂度可以做到 \(O(nm^3\log n+qm^2\log n)\)。
代码
#include<bits/stdc++.h>
#define rep(i,a,b) for(register int i=(a);i<=(b);++i)
#define endl '\n'
using namespace std;
typedef long long ll;
const ll MAXN=1e5+3;
const ll MAXM=12;
int m,n,Q,A[MAXM][MAXN],B[MAXM][MAXN];
struct node{
ll l,r,c[MAXM][MAXM];
#define lc(u) (u<<1)
#define rc(u) (u<<1|1)
}t[MAXN*4];
ll ans[MAXM],sans[MAXN];
inline void merge(ll u,ll l,bool fst){
rep(i,1,m){
sans[i]=1e18;
}
rep(j,1,m){
rep(i,1,m){
sans[i]=min(sans[i],ans[j]+(fst?0:A[j][l-1])+t[u].c[j][i]);
}
}
rep(i,1,m){
ans[i]=sans[i];
}
}
inline void push_up(ll u){
rep(i,1,m){
rep(j,1,m){
t[u].c[i][j]=1e18;
}
}
rep(k,1,m){
rep(i,1,m){
rep(j,1,m){
t[u].c[i][j]=min(t[u].c[i][j],t[lc(u)].c[i][k]+A[k][(t[u].l+t[u].r)>>1]+t[rc(u)].c[k][j]);
}
}
}
}
ll L[MAXN][MAXM][MAXM],R[MAXN][MAXM][MAXM];
ll v[MAXN][MAXM][MAXM];
void floyd_f(ll id){
rep(k,1,m){
rep(i,1,m){
rep(j,1,m){
v[id][i][j]=min(v[id][i][j],v[id][i][k]+v[id][k][j]);
}
}
}
}
void floyd(ll id,bool r){
if(!r){
rep(k,1,m){
rep(i,1,m){
rep(j,1,m){
L[id][i][j]=min(L[id][i][j],L[id][i][k]+L[id][k][j]);
}
}
}
return;
}
rep(k,1,m){
rep(i,1,m){
rep(j,1,m){
R[id][i][j]=min(R[id][i][j],R[id][i][k]+R[id][k][j]);
}
}
}
}
void build(ll u,ll l,ll r){
t[u].l=l;
t[u].r=r;
if(l==r){
memcpy(t[u].c,v[l],sizeof t[u].c);
return;
}
ll mid=(l+r)>>1;
build(lc(u),l,mid);
build(rc(u),mid+1,r);
push_up(u);
}
void query(ll u,ll l,ll r,ll ql,ll qr){
if(ql<=l&&r<=qr){
merge(u,l,l==ql);
return;
}
ll mid=(l+r)>>1;
if(ql<=mid){
query(lc(u),l,mid,ql,qr);
}
if(mid+1<=qr){
query(rc(u),mid+1,r,ql,qr);
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>m>>n>>Q;
rep(i,1,m){
rep(j,1,n-1){
cin>>A[i][j];
}
}
rep(i,1,m-1){
rep(j,1,n){
cin>>B[i][j];
}
}
memset(L,0x3f,sizeof L);
memset(R,0x3f,sizeof R);
rep(i,1,n){
memcpy(L[i],L[i-1],sizeof L[i]);
if(i>1){
rep(j,1,m){
rep(k,1,m){
L[i][j][k]+=A[j][i-1]+A[k][i-1];
}
}
}
rep(j,1,m){
L[i][j][j]=0;
L[i][j][j+1]=L[i][j+1][j]=min(L[i][j][j+1],ll(B[j][i]));
}
floyd(i,0);
}
for(int i=n;i>=1;--i){
memcpy(R[i],R[i+1],sizeof R[i]);
if(i<n){
rep(j,1,m){
rep(k,1,m){
R[i][j][k]+=A[j][i]+A[k][i];
}
}
}
rep(j,1,m){
R[i][j][j]=0;
R[i][j][j+1]=R[i][j+1][j]=min(R[i][j][j+1],ll(B[j][i]));
}
floyd(i,1);
rep(j,1,m){
rep(k,1,m){
v[i][j][k]=min(L[i][j][k],R[i][j][k]);
}
}
floyd_f(i);
}
build(1,1,n);
rep(_,1,Q){
ll a,b,p,q;
cin>>a>>b>>p>>q;
if(b>q){
swap(a,p);
swap(b,q);
}
memset(ans,0x3f,sizeof ans);
ans[a]=0;
query(1,1,n,b,q);
cout<<ans[p]<<endl;
}
return 0;
}
来源链接：https://www.cnblogs.com/tanghg/p/18711074/solution-25BJWCB2A
没有回复内容