[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;

}

巴特西

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

题解

最新文章

热门文章

巴特西

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

题解

最新文章

热门文章

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