[BZOJ2143]飞飞侠 并查集优化最短路

链接

题解

首先很容易想到对每个点暴力跑Dijkstra，但是这样边数是 \(N^4\) 的，考虑优化

发现每次松弛的时候，都要把整个地图扫一遍，每个节点都要重复扫很多次，如果我们在一个点不会再被更新的时候，用并查集跳过去，那么就可以降低复杂度

如果将点插入堆时，比较 \(dis[i]+w[i]\) 而不是 \(dis[i]\) ，这样可以保证一个点被更新后不会再一次被更新。

现在证明上述结论，以及这样做仍然可以得到正确的最短路。

假设点 \(x\) 已经得到了最短路，证明用该点更新的 \(y\) 也得到了最短路

反证，假设存在路径 $ x’ \to y$ 使 \(dis[y]\) 更小，且在 \(x\) 更新 \(y\) 之后，那么有 \(dis[x']+w[x']< dis[x]+w[x]\) ，因为 \(x'\) 在 \(x\) 之后，有 \(dis[x']+w[x']\ge dis[x]+w[x]\)，两式矛盾，运用数学归纳法，可知上述结论成立，以及起点 \(s\) 到每一点的最短路径就是 \(dis[i]\)

因此，用并查集合并已经更新过的点，再一次扫描到的时候，直接跳过即可，边数优化成 \(N^2\)

复杂度 \(O(N^2logN)\)

#include<bits/stdc++.h>
#define REP(i,a,b) for(int i(a);i<=(b);++i)
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>pii;
inline int read(){char c,p=0;int w;
    while(isspace(c=getchar()));if(c=='-')p=1,c=getchar();w=c&15;
    while(isdigit(c=getchar()))w=w*10+(c&15);return p?-w:w;
}
template<typename T,typename U>inline bool smin(T&x,const U&y){return x>y?x=y,1:0;}
template<typename T,typename U>inline bool smax(T&x,const U&y){return x<y?x=y,1:0;}
const int N=155;
int n,m,a[N][N],b[N][N],d[3][N][N],vis[N][N],fa[N][N];
priority_queue< pair<int,pii> >q;
#define xx first
#define yy second
inline int find(int*f,int x){return f[x]?f[x]=find(f,f[x]):x;}
inline void solve(int d[N][N],pii s){
    REP(i,1,n)REP(j,1,m)d[i][j]=1e9;
    memset(vis,0,sizeof vis);
    memset(fa,0,sizeof fa);
    d[s.xx][s.yy]=0;
    q.push(make_pair(-a[s.xx][s.yy],s));fa[s.xx][s.yy]=s.yy+1;
    while(!q.empty()){
        pii u=q.top().yy;q.pop();
        const int&x=u.xx,&y=u.yy;
        if(vis[x][y])continue;vis[x][y]=1;
        int lx=max(1,x-b[x][y]),rx=min(n,x+b[x][y]);
        REP(i,lx,rx){
            int t=b[x][y]-abs(i-x),ly=max(1,y-t),ry=min(m,y+t);
            for(int j=find(fa[i],ly);j<=ry;j=find(fa[i],j)){
                if(smin(d[i][j],d[x][y]+a[x][y]))q.push(make_pair(-d[i][j]-a[i][j],pii(i,j)));
                fa[i][j]=j+1;
            }
            
        }
    }
}
pii s[3];
const char ss[]="XYZ";
int main(){
    n=read(),m=read();
    REP(i,1,n)REP(j,1,m)b[i][j]=read(); 
    REP(i,1,n)REP(j,1,m)a[i][j]=read();
    REP(i,0,2)s[i].xx=read(),s[i].yy=read(),solve(d[i],s[i]);
    int dis=1e9;
    int ans=-1;
    REP(i,0,2){ 
        #define d(p) d[p][s[i].xx][s[i].yy]
        if(smin(dis,d(0)+d(1)+d(2)))ans=i;
    }
    if(~ans)printf("%c\n%d",ss[ans],dis);
    else puts("NO");
    return 0;
}