「BZOJ2304」[APIO2011] 寻路path

2014年8月5日7,0700

Description

TooDee是一块二维格子状的土地（就像著名的笛卡尔坐标系那样），在这里
生活着很多可爱的Dee。Dee是像蜜蜂一样的小动物，它们只在二维活动，而且
它们非常的文明开化。TooDee 的蜂窝和正常世界的蜂窝也是很不一样的，它们
是矩形的且它们的边平行于TooDee的地理坐标系，就是说矩形的边或者是东西
走向，或者是南北走向。
因为 Dees 是很高级的生物，它们有很多固定的飞行轨道，这些轨道由一些
平行于坐标轴的线段组成，线段只会在经纬度都是整数的点相交。 Dee在TooDee
飞行时必须遵守以下规则（请记住TooDee中所有点的经纬度都是整数）：
1 如果当前在点(XS, YS)，则下步只能飞到四个邻点 (XS, YS – 1), (XS, YS + 1),
(XS – 1, YS ), (XS + 1, YS )；
2 不可以进入蜂巢；
3 只能在蜂巢的角或者边上改变飞行方向；
4 开始的时候可以向任何方向飞；
今晚是公共财政大臣Deeficer的女儿的生日，她想尽早回家，请帮她找到最
快的回家路径。假设她每秒可以飞行一个单位的距离。

Input

每个测试点包含多组数据。
输入的第一行包含一个整数T，表示测试数据的组数。接下来依次描述这T
组数据，相邻的两组之间使用一个空行分隔。测试数据不多于20组。
对于每组数据，第一行包含4个整数 xs, ys, xt, yt，表示Deeficer 的办公室和
家的坐标分别为(xs, ys)和(xt, yt)。第二行包含一个整数n，表示蜂巢的个数。接下
来的n行描述所有的蜂巢，其中第 i行包含 4 个整数xi1, yi1, xi2, yi2，表示第i个
蜂巢两个对角的坐标分别为(xi1, yi1)和(xi2, yi2)。
任何两个蜂巢都不会相交，也不会接触（在角上也不会接触）。办公室和家
处在不同的位置。每个蜂巢的面积为正。

Output

对于每一组数据，输出一个整数，表示Deeficer 最快回家的时间（单位为秒），
如果她无法按规则回家，则输出“No Path”。

对于100%的测试数据，1 ≤ n ≤ 1000，所有坐标都是不超过10^9
的整数；

Sample Input

2
1 7 7 8
2
2 5 3 8
4 10 6 7
2 1 5 4
1
3 1 4 3

Sample Output

9
No Path

题解

http://wenku.baidu.com/link?url=xJBtwotOM1MjW38-sIQUydPsyCFpCmcuYGIpCCzEhDnyJnpa7cQ_7JmcH1IbZ0rsLKF_bST0jQu2xSDb55755lvsedIqzu0kT32S8FXWB_7

n^2的做法。。。bzoj数据太强了根本过不去。。。

暴力大概就是上下左右扫描乱找

#include<iostream>
#include<cstdio>
#include<iostream>
#include<cstring>
#include<cstdlib>
#define ll long long
#define llinf 8000000000000000000LL
#define inf 0x7fffffff
#define p(i,j) (i-1)*4+j+2
using namespace std;
inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}
    return x*f;
}
int T,n,m,cnt;
int xs,ys,xt,yt;
int head[2000005],q[4000005];
bool inq[4000005];
ll dis[4000005];
struct re{int x1,x2,y1,y2;}r[1005];
struct edge{int to,next,v;}e[10000005];
struct data{int x,y;}p[4000005];
void ins(int u,int v,int w)
{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}
void insert(int u,int v,int w)
{ins(u,v,w);ins(v,u,w);}
int spfa()
{
    int t=0,w=1,now;
    for(int i=1;i<=m;i++)dis[i]=llinf;
    dis[1]=0;inq[1]=1;q[0]=1;
    while(t!=w)
    {
        now=q[t];t++;if(t==4000005)t=0;
        for(int i=head[now];i;i=e[i].next)
            if(e[i].v+dis[now]<dis[e[i].to])
            {
                dis[e[i].to]=dis[now]+e[i].v;
                if(!inq[e[i].to])
                {
                    inq[e[i].to]=1;
                    q[w++]=e[i].to;
                    if(w==4000005)w=0;
                }
            }
        inq[now]=0;
    }
}
void add(int x,int y){p[++m].x=x;p[m].y=y;}
void find1(int x,int y,int k)
{
	int mn1=inf,mn2=inf;
	int tmp1=-1,tmp2=-1;
	for(int i=1;i<=m;i++)
	{
	    if(p[i].y!=y||k==i)continue;
	    if(p[i].x<=x&&x-p[i].x<mn1){tmp1=i;mn1=x-p[i].x;}
	    if(p[i].x>=x&&p[i].x-x<mn2){tmp2=i;mn2=p[i].x-x;}
    }
    if(tmp1!=-1)insert(k,tmp1,mn1);if(tmp2!=-1)insert(k,tmp2,mn2);
}
void find2(int x,int y,int k)
{
	int mn1=inf,mn2=inf;
	int tmp1=-1,tmp2=-1;
	for(int i=1;i<=m;i++)
	{
	    if(p[i].x!=x||k==i)continue;
	    if(p[i].y<=y&&y-p[i].y<mn1){tmp1=i;mn1=y-p[i].y;}
	    if(p[i].y>=y&&p[i].y-y<mn2){tmp2=i;mn2=p[i].y-y;}
    }
    if(tmp1!=-1)insert(k,tmp1,mn1);if(tmp2!=-1)insert(k,tmp2,mn2);
}
void build1(int x,int y,int mark)
{
     int mn=inf,tmp=-1;
     for(int i=1;i<=n;i++)
        if(r[i].x1<=x&&r[i].x2>=x&&r[i].y1>y&&r[i].y1-y<mn)
           mn=r[i].y1-y,tmp=i;
     if(tmp!=-1)
     {
         add(x,r[tmp].y1);
         insert(mark,m,mn);
         find1(x,r[tmp].y1,m);
     }
}
void build2(int x,int y,int mark)
{
     int mn=inf,tmp=-1;
     for(int i=1;i<=n;i++)
        if(r[i].x1<=x&&r[i].x2>=x&&r[i].y2<y&&y-r[i].y2<mn)
           mn=y-r[i].y2,tmp=i;
     if(tmp!=-1)
     {
         add(x,r[tmp].y2);
         insert(mark,m,mn);
         find1(x,r[tmp].y2,m);
     }
}
void build3(int x,int y,int mark)
{
     int mn=inf,tmp=-1;
     for(int i=1;i<=n;i++)
        if(r[i].y1<=y&&r[i].y2>=y&&r[i].x1>x&&r[i].x1-x<mn)
           mn=r[i].x1-x,tmp=i;
     if(tmp!=-1)
     {
         add(r[tmp].x1,y);
         insert(mark,m,mn);
         find2(r[tmp].x1,y,m);
     }
}
void build4(int x,int y,int mark)
{
     int mn=inf,tmp=-1;
     for(int i=1;i<=n;i++)
        if(r[i].y1<=y&&r[i].y2>=y&&r[i].x2<x&&x-r[i].x2<mn)
           mn=x-r[i].x2,tmp=i;
     if(tmp!=-1)
     {
         add(r[tmp].x2,y);
         insert(mark,m,mn);
         find2(r[tmp].x2,y,m);
     }
}
void build(int x)
{
     insert(p(x,1),p(x,2),r[x].x2-r[x].x1);
     insert(p(x,1),p(x,3),r[x].y2-r[x].y1);
     insert(p(x,4),p(x,3),r[x].x2-r[x].x1);
     insert(p(x,2),p(x,4),r[x].y2-r[x].y1);
     build2(r[x].x1,r[x].y1,p(x,1));build4(r[x].x1,r[x].y1,p(x,1));
     build2(r[x].x2,r[x].y1,p(x,2));build3(r[x].x2,r[x].y1,p(x,2));
     build1(r[x].x1,r[x].y2,p(x,3));build4(r[x].x1,r[x].y2,p(x,3));
     build1(r[x].x2,r[x].y2,p(x,4));build3(r[x].x2,r[x].y2,p(x,4));
}
int main()
{
    T=read();
    while(T--)
    {
         cnt=m=0;
         memset(head,0,sizeof(head));
         xs=read();ys=read();add(xs,ys);
         xt=read();yt=read();add(xt,yt);
         n=read();
         for(int i=1;i<=n;i++)
         {
             r[i].x1=read();r[i].y1=read();
             r[i].x2=read();r[i].y2=read();
             add(r[i].x1,r[i].y1);add(r[i].x2,r[i].y1);
             add(r[i].x1,r[i].y2);add(r[i].x2,r[i].y2);
         }
         for(int i=1;i<=n;i++)build(i);
         build1(xs,ys,1);build2(xs,ys,1);build3(xs,ys,1);build4(xs,ys,1);
         build1(xt,yt,2);build2(xt,yt,2);build3(xt,yt,2);build4(xt,yt,2);
         find1(xs,ys,1);find2(xs,ys,1);
         spfa();
         if(dis[2]!=llinf)printf("%lld\n",dis[2]);
         else printf("No Path\n");
    }
    return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

#include<iostream>

#include<cstdio>

#include<iostream>

#include<cstring>

#include<cstdlib>

#define ll long long

#define llinf 8000000000000000000LL

#define inf 0x7fffffff

#define p(i,j) (i-1)*4+j+2

using namespace std;

inline int read()

{

char ch=getchar();

int f=1,x=0;

while(!(ch>='0'&&ch<='9')){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+(ch-'0');ch=getchar();}

return x*f;

}

int T,n,m,cnt;

int xs,ys,xt,yt;

int head[2000005],q[4000005];

bool inq[4000005];

ll dis[4000005];

struct re{int x1,x2,y1,y2;}r[1005];

struct edge{int to,next,v;}e[10000005];

struct data{int x,y;}p[4000005];

void ins(int u,int v,int w)

{e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;e[cnt].v=w;}

void insert(int u,int v,int w)

{ins(u,v,w);ins(v,u,w);}

int spfa()

{

int t=0,w=1,now;

for(int i=1;i<=m;i++)dis[i]=llinf;

dis[1]=0;inq[1]=1;q[0]=1;

while(t!=w)

{

now=q[t];t++;if(t==4000005)t=0;

for(int i=head[now];i;i=e[i].next)

if(e[i].v+dis[now]<dis[e[i].to])

{

dis[e[i].to]=dis[now]+e[i].v;

if(!inq[e[i].to])

{

inq[e[i].to]=1;

q[w++]=e[i].to;

if(w==4000005)w=0;

}

inq[now]=0;

}

void add(int x,int y){p[++m].x=x;p[m].y=y;}

void find1(int x,int y,int k)

{

int mn1=inf,mn2=inf;

int tmp1=-1,tmp2=-1;

for(int i=1;i<=m;i++)

{

if(p[i].y!=y||k==i)continue;

if(p[i].x<=x&&x-p[i].x<mn1){tmp1=i;mn1=x-p[i].x;}

if(p[i].x>=x&&p[i].x-x<mn2){tmp2=i;mn2=p[i].x-x;}

}

if(tmp1!=-1)insert(k,tmp1,mn1);if(tmp2!=-1)insert(k,tmp2,mn2);

}

void find2(int x,int y,int k)

{

int mn1=inf,mn2=inf;

int tmp1=-1,tmp2=-1;

for(int i=1;i<=m;i++)

{

if(p[i].x!=x||k==i)continue;

if(p[i].y<=y&&y-p[i].y<mn1){tmp1=i;mn1=y-p[i].y;}

if(p[i].y>=y&&p[i].y-y<mn2){tmp2=i;mn2=p[i].y-y;}

}

if(tmp1!=-1)insert(k,tmp1,mn1);if(tmp2!=-1)insert(k,tmp2,mn2);

}

void build1(int x,int y,int mark)

{

int mn=inf,tmp=-1;

for(int i=1;i<=n;i++)

if(r[i].x1<=x&&r[i].x2>=x&&r[i].y1>y&&r[i].y1-y<mn)

mn=r[i].y1-y,tmp=i;

if(tmp!=-1)

{

add(x,r[tmp].y1);

insert(mark,m,mn);

find1(x,r[tmp].y1,m);

}

void build2(int x,int y,int mark)

{

int mn=inf,tmp=-1;

for(int i=1;i<=n;i++)

if(r[i].x1<=x&&r[i].x2>=x&&r[i].y2<y&&y-r[i].y2<mn)

mn=y-r[i].y2,tmp=i;

if(tmp!=-1)

{

add(x,r[tmp].y2);

insert(mark,m,mn);

find1(x,r[tmp].y2,m);

}

void build3(int x,int y,int mark)

{

int mn=inf,tmp=-1;

for(int i=1;i<=n;i++)

if(r[i].y1<=y&&r[i].y2>=y&&r[i].x1>x&&r[i].x1-x<mn)

mn=r[i].x1-x,tmp=i;

if(tmp!=-1)

{

add(r[tmp].x1,y);

insert(mark,m,mn);

find2(r[tmp].x1,y,m);

}

void build4(int x,int y,int mark)

{

int mn=inf,tmp=-1;

for(int i=1;i<=n;i++)

if(r[i].y1<=y&&r[i].y2>=y&&r[i].x2<x&&x-r[i].x2<mn)

mn=x-r[i].x2,tmp=i;

if(tmp!=-1)

{

add(r[tmp].x2,y);

insert(mark,m,mn);

find2(r[tmp].x2,y,m);

}

void build(int x)

{

insert(p(x,1),p(x,2),r[x].x2-r[x].x1);

insert(p(x,1),p(x,3),r[x].y2-r[x].y1);

insert(p(x,4),p(x,3),r[x].x2-r[x].x1);

insert(p(x,2),p(x,4),r[x].y2-r[x].y1);

build2(r[x].x1,r[x].y1,p(x,1));build4(r[x].x1,r[x].y1,p(x,1));

build2(r[x].x2,r[x].y1,p(x,2));build3(r[x].x2,r[x].y1,p(x,2));

build1(r[x].x1,r[x].y2,p(x,3));build4(r[x].x1,r[x].y2,p(x,3));

build1(r[x].x2,r[x].y2,p(x,4));build3(r[x].x2,r[x].y2,p(x,4));

}

int main()

{

T=read();

while(T--)

{

cnt=m=0;

memset(head,0,sizeof(head));

xs=read();ys=read();add(xs,ys);

xt=read();yt=read();add(xt,yt);

n=read();

for(int i=1;i<=n;i++)

{

r[i].x1=read();r[i].y1=read();

r[i].x2=read();r[i].y2=read();

add(r[i].x1,r[i].y1);add(r[i].x2,r[i].y1);

add(r[i].x1,r[i].y2);add(r[i].x2,r[i].y2);

}

for(int i=1;i<=n;i++)build(i);

build1(xs,ys,1);build2(xs,ys,1);build3(xs,ys,1);build4(xs,ys,1);

build1(xt,yt,2);build2(xt,yt,2);build3(xt,yt,2);build4(xt,yt,2);

find1(xs,ys,1);find2(xs,ys,1);

spfa();

if(dis[2]!=llinf)printf("%lld\n",dis[2]);

else printf("No Path\n");

}

return 0;

}

正解TMD我写了两遍用了n个小时T T

题解中只有几句话，简直了说起来似乎很简单，但是问题会比较多T T

例如这个新建的点是要上下延伸的，这我没有想到很好的办法，只能再对于每个xy坐标建个平衡树，每次把点放进去找相同x/y坐标的最近点

对于起点和终点的处理T T，如果当做矩形的话那么起点终点落在边或者角上是不好处理的

那么可以暴力找他们最近的矩形，类似上面一样连边，注意特判起点可以直接到终点的情况

然后最短路用dijkstra

记得vfk似乎说过这道题代码超过6k的都是弱菜，好吧我超过了

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<queue>
#define ll long long 
#define inf 2000000000
#define llinf 8000000000000000000LL
#define pa pair<ll,int>
using namespace std;
inline int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int xs,ys,xt,yt,st,ed;
int n,s,T,cnt,sz;
int mark[2005][2005],sx[20005],sy[20005];
int x1[1005],ya[1005],x2[1005],y2[1005],d[2][2005],last[20005];
bool vis[20005]; 
ll dis[20005];
set <int> x[2005],y[2005];
struct edge{int to,next,v;}e[500005];
struct ed1{int ya,y2,x;}a[2005];
struct ed2{int x1,x2,y;}b[2005];
struct seg{int l,r,tag,v;}t[8005];
inline bool cp1(ed1 a,ed1 b){return a.x<b.x;}
inline bool cp2(ed1 a,ed1 b){return a.x>b.x;}
inline bool cp3(ed2 a,ed2 b){return a.y<b.y;}
inline bool cp4(ed2 a,ed2 b){return a.y>b.y;}
void insert(int u,int v,int w)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;
	e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;
}
int find(bool f,int x)
{
	int l=1,r=2*n+2;
	while(l<=r)
	{
		int mid=(l+r)>>1;
		if(d[f][mid]==x)return mid;
		else if(d[f][mid]<x)l=mid+1;
		else r=mid-1;
	}
}
void build(int k,int l,int r)
{
	t[k].l=l;t[k].r=r;t[k].v=t[k].tag=0;
	if(l==r)return;
	int mid=(l+r)>>1;
	build(k<<1,l,mid);build(k<<1|1,mid+1,r);
}
void pushdown(int k)
{
	if(t[k].l==t[k].r||!t[k].tag)return;
	int tag=t[k].tag;t[k].tag=0;
	t[k<<1].tag=t[k<<1].v=tag;
	t[k<<1|1].tag=t[k<<1|1].v=tag;
}
void modify(int k,int x,int y,int val)
{
	pushdown(k);int l=t[k].l,r=t[k].r;
	if(l==x&&y==r){t[k].tag=t[k].v=val;return;}
	int mid=(l+r)>>1;
	if(y<=mid)modify(k<<1,x,y,val);
	else if(x>mid)modify(k<<1|1,x,y,val);
	else modify(k<<1,x,mid,val),modify(k<<1|1,mid+1,y,val);
}
int query(int k,int x)
{
	pushdown(k);int l=t[k].l,r=t[k].r;
	if(l==r)return t[k].v;
	int mid=(l+r)>>1;
	if(x<=mid)return query(k<<1,x);
	else return query(k<<1|1,x);
}
inline int get(int a,int b)
{
	if(mark[a][b])return mark[a][b];
	sz++;mark[a][b]=sz;
	sx[sz]=a;sy[sz]=b;
	return sz;
}
void add(int x1,int ya,int x2,int y2)
{
	if(x1==x2&&ya==y2)return;
	int t1=get(x1,ya),t2=get(x2,y2);
    insert(t1,t2,abs(d[0][x1]-d[0][x2]+d[1][ya]-d[1][y2]));
}
inline void spreadx(int a,int b)
{
	int r=*y[b].lower_bound(a);if(r==a)return;
	int l=*--y[b].lower_bound(a);
	if(l!=-inf)add(a,b,l,b);if(r!=inf)add(a,b,r,b);
}
inline void spready(int a,int b)
{
	int r=*x[a].lower_bound(b);if(r==b)return;
	int l=*--x[a].lower_bound(b);
	if(l!=-inf)add(a,b,a,l);if(r!=inf)add(a,b,a,r);
}
inline void put(int a,int b)
{
	x[a].insert(b);y[b].insert(a);
}
void solve(int a,int b,bool f)
{
	int mx=0,mn=inf;
	if(!f&&xs==xt){if(yt>ys)mn=yt;else mx=yt;}
	for(int i=1;i<=n;i++)
	{
		if(x1[i]>a||x2[i]<a)continue;
		if(ya[i]>=b)mn=min(ya[i],mn);
		if(y2[i]<=b)mx=max(y2[i],mx);
	}
	if(mx)add(a,b,a,mx),spreadx(a,mx),put(a,mx);
	if(mn!=inf)add(a,b,a,mn),spreadx(a,mn),put(a,mn);
	mx=0,mn=inf;
	if(!f&&ys==yt){if(xt>xs)mn=xt;else mx=xt;}
	for(int i=1;i<=n;i++)
	{
		if(ya[i]>b||y2[i]<b)continue;
		if(x1[i]>=a)mn=min(x1[i],mn);
		if(x2[i]<=a)mx=max(x2[i],mx);
	}
	if(mx)add(a,b,mx,b),spready(mx,b),put(mx,b);
	if(mn!=inf)add(a,b,mn,b),spready(mn,b),put(mn,b);
}
void sol1()
{
	build(1,1,2*n+2);
	for(int i=1;i<=s;i++)
	{
		int ya=a[i].ya,y2=a[i].y2,x=a[i].x;
		int t1=query(1,ya),t2=query(1,y2);
		if(t1)add(x,ya,t1,ya),spready(t1,ya),put(t1,ya);
		if(t2)add(x,y2,t2,y2),spready(t2,y2),put(t2,y2);
		modify(1,ya,y2,x);
	}
}
void sol2()
{
	build(1,1,2*n+2);
	for(int i=1;i<=s;i++)
	{
		int x1=b[i].x1,x2=b[i].x2,y=b[i].y;
		int t1=query(1,x1),t2=query(1,x2);
		if(t1)add(x1,y,x1,t1),spreadx(x1,t1),put(x1,t1);
		if(t2)add(x2,y,x2,t2),spreadx(x2,t2),put(x2,t2);
		modify(1,x1,x2,y);
	}
}
void buildmap()
{
    sort(a+1,a+s+1,cp1);sol1();sort(a+1,a+s+1,cp2);sol1();
	sort(b+1,b+s+1,cp3);sol2();sort(b+1,b+s+1,cp4);sol2();
}
void dijkstra()
{	
	priority_queue<pa,vector<pa>,greater<pa> > q;
	for(int i=1;i<=sz;i++)dis[i]=llinf;
	dis[st]=0;q.push(make_pair(0,st));
	while(!q.empty())
	{
		int now=q.top().second;q.pop();
		if(vis[now])continue;vis[now]=1;
		for(int i=last[now];i;i=e[i].next)		
			if(dis[now]+e[i].v<dis[e[i].to])
			{
	   			dis[e[i].to]=dis[now]+e[i].v;
	   			q.push(make_pair(dis[e[i].to],e[i].to));
			}
	}
}
int main()
{
	T=read();
	while(T--)
	{
		for(int i=1;i<=sz;i++)mark[sx[i]][sy[i]]=vis[i]=last[i]=0;
		cnt=sz=s=0;
		xs=read();ys=read();xt=read();yt=read();n=read();
		for(int i=1;i<=2*n+2;i++)
		{
			x[i].clear();x[i].insert(inf);x[i].insert(-inf);
			y[i].clear();y[i].insert(inf);y[i].insert(-inf);
		}
		for(int i=1;i<=n;i++)
		{
			x1[i]=d[0][2*i-1]=read();ya[i]=d[1][2*i-1]=read();
			x2[i]=d[0][2*i]=read();y2[i]=d[1][2*i]=read();
			if(x1[i]>x2[i])swap(x1[i],x2[i]);
			if(ya[i]>y2[i])swap(ya[i],y2[i]);
		}	
		d[0][2*n+1]=xs;d[0][2*n+2]=xt;d[1][2*n+1]=ys;d[1][2*n+2]=yt;
		sort(d[0]+1,d[0]+2*n+3);sort(d[1]+1,d[1]+2*n+3);
		for(int i=1;i<=n;i++)
		{
			x1[i]=find(0,x1[i]),x2[i]=find(0,x2[i]);
			ya[i]=find(1,ya[i]),y2[i]=find(1,y2[i]);
			++s;
			b[s].y=ya[i];b[s].x1=x1[i];b[s].x2=x2[i];
			a[s].x=x1[i];a[s].ya=ya[i];a[s].y2=y2[i];
			++s;
			b[s].y=y2[i];b[s].x1=x1[i];b[s].x2=x2[i];
			a[s].x=x2[i];a[s].ya=ya[i];a[s].y2=y2[i];
			put(x1[i],ya[i]);put(x2[i],y2[i]);
			put(x1[i],y2[i]);put(x2[i],ya[i]);
		}
		buildmap();
		xs=find(0,xs);xt=find(0,xt);ys=find(1,ys);yt=find(1,yt);
		solve(xs,ys,0);solve(xt,yt,1);
		st=mark[xs][ys];ed=mark[xt][yt];
		if(!st||!ed){puts("No Path");continue;}
		dijkstra();
		if(dis[ed]!=llinf)printf("%lld\n",dis[ed]);
		else puts("No Path");
	}
	return 0;
}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

185

186

187

188

189

190

191

192

193

194

195

196

197

198

199

200

201

202

203

204

205

206

207

208

209

210

211

212

213

214

215

216

217

218

219

220

221

222

223

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<set>

#include<queue>

#define ll long long

#define inf 2000000000

#define llinf 8000000000000000000LL

#define pa pair<ll,int>

using namespace std;

inline int read()

{

int x=0,f=1;char ch=getchar();

while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x*f;

}

int xs,ys,xt,yt,st,ed;

int n,s,T,cnt,sz;

int mark[2005][2005],sx[20005],sy[20005];

int x1[1005],ya[1005],x2[1005],y2[1005],d[2][2005],last[20005];

bool vis[20005];

ll dis[20005];

set <int> x[2005],y[2005];

struct edge{int to,next,v;}e[500005];

struct ed1{int ya,y2,x;}a[2005];

struct ed2{int x1,x2,y;}b[2005];

struct seg{int l,r,tag,v;}t[8005];

inline bool cp1(ed1 a,ed1 b){return a.x<b.x;}

inline bool cp2(ed1 a,ed1 b){return a.x>b.x;}

inline bool cp3(ed2 a,ed2 b){return a.y<b.y;}

inline bool cp4(ed2 a,ed2 b){return a.y>b.y;}

void insert(int u,int v,int w)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[cnt].v=w;

e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;e[cnt].v=w;

}

int find(bool f,int x)

{

int l=1,r=2*n+2;

while(l<=r)

{

int mid=(l+r)>>1;

if(d[f][mid]==x)return mid;

else if(d[f][mid]<x)l=mid+1;

else r=mid-1;

}

void build(int k,int l,int r)

{

t[k].l=l;t[k].r=r;t[k].v=t[k].tag=0;

if(l==r)return;

int mid=(l+r)>>1;

build(k<<1,l,mid);build(k<<1|1,mid+1,r);

}

void pushdown(int k)

{

if(t[k].l==t[k].r||!t[k].tag)return;

int tag=t[k].tag;t[k].tag=0;

t[k<<1].tag=t[k<<1].v=tag;

t[k<<1|1].tag=t[k<<1|1].v=tag;

}

void modify(int k,int x,int y,int val)

{

pushdown(k);int l=t[k].l,r=t[k].r;

if(l==x&&y==r){t[k].tag=t[k].v=val;return;}

int mid=(l+r)>>1;

if(y<=mid)modify(k<<1,x,y,val);

else if(x>mid)modify(k<<1|1,x,y,val);

else modify(k<<1,x,mid,val),modify(k<<1|1,mid+1,y,val);

}

int query(int k,int x)

{

pushdown(k);int l=t[k].l,r=t[k].r;

if(l==r)return t[k].v;

int mid=(l+r)>>1;

if(x<=mid)return query(k<<1,x);

else return query(k<<1|1,x);

}

inline int get(int a,int b)

{

if(mark[a][b])return mark[a][b];

sz++;mark[a][b]=sz;

sx[sz]=a;sy[sz]=b;

return sz;

}

void add(int x1,int ya,int x2,int y2)

{

if(x1==x2&&ya==y2)return;

int t1=get(x1,ya),t2=get(x2,y2);

insert(t1,t2,abs(d[0][x1]-d[0][x2]+d[1][ya]-d[1][y2]));

}

inline void spreadx(int a,int b)

{

int r=*y[b].lower_bound(a);if(r==a)return;

int l=*--y[b].lower_bound(a);

if(l!=-inf)add(a,b,l,b);if(r!=inf)add(a,b,r,b);

}

inline void spready(int a,int b)

{

int r=*x[a].lower_bound(b);if(r==b)return;

int l=*--x[a].lower_bound(b);

if(l!=-inf)add(a,b,a,l);if(r!=inf)add(a,b,a,r);

}

inline void put(int a,int b)

{

x[a].insert(b);y[b].insert(a);

}

void solve(int a,int b,bool f)

{

int mx=0,mn=inf;

if(!f&&xs==xt){if(yt>ys)mn=yt;else mx=yt;}

for(int i=1;i<=n;i++)

{

if(x1[i]>a||x2[i]<a)continue;

if(ya[i]>=b)mn=min(ya[i],mn);

if(y2[i]<=b)mx=max(y2[i],mx);

}

if(mx)add(a,b,a,mx),spreadx(a,mx),put(a,mx);

if(mn!=inf)add(a,b,a,mn),spreadx(a,mn),put(a,mn);

mx=0,mn=inf;

if(!f&&ys==yt){if(xt>xs)mn=xt;else mx=xt;}

for(int i=1;i<=n;i++)

{

if(ya[i]>b||y2[i]<b)continue;

if(x1[i]>=a)mn=min(x1[i],mn);

if(x2[i]<=a)mx=max(x2[i],mx);

}

if(mx)add(a,b,mx,b),spready(mx,b),put(mx,b);

if(mn!=inf)add(a,b,mn,b),spready(mn,b),put(mn,b);

}

void sol1()

{

build(1,1,2*n+2);

for(int i=1;i<=s;i++)

{

int ya=a[i].ya,y2=a[i].y2,x=a[i].x;

int t1=query(1,ya),t2=query(1,y2);

if(t1)add(x,ya,t1,ya),spready(t1,ya),put(t1,ya);

if(t2)add(x,y2,t2,y2),spready(t2,y2),put(t2,y2);

modify(1,ya,y2,x);

}

void sol2()

{

build(1,1,2*n+2);

for(int i=1;i<=s;i++)

{

int x1=b[i].x1,x2=b[i].x2,y=b[i].y;

int t1=query(1,x1),t2=query(1,x2);

if(t1)add(x1,y,x1,t1),spreadx(x1,t1),put(x1,t1);

if(t2)add(x2,y,x2,t2),spreadx(x2,t2),put(x2,t2);

modify(1,x1,x2,y);

}

void buildmap()

{

sort(a+1,a+s+1,cp1);sol1();sort(a+1,a+s+1,cp2);sol1();

sort(b+1,b+s+1,cp3);sol2();sort(b+1,b+s+1,cp4);sol2();

}

void dijkstra()

{

priority_queue<pa,vector<pa>,greater<pa> > q;

for(int i=1;i<=sz;i++)dis[i]=llinf;

dis[st]=0;q.push(make_pair(0,st));

while(!q.empty())

{

int now=q.top().second;q.pop();

if(vis[now])continue;vis[now]=1;

for(int i=last[now];i;i=e[i].next)

if(dis[now]+e[i].v<dis[e[i].to])

{

dis[e[i].to]=dis[now]+e[i].v;

q.push(make_pair(dis[e[i].to],e[i].to));

}

int main()

{

T=read();

while(T--)

{

for(int i=1;i<=sz;i++)mark[sx[i]][sy[i]]=vis[i]=last[i]=0;

cnt=sz=s=0;

xs=read();ys=read();xt=read();yt=read();n=read();

for(int i=1;i<=2*n+2;i++)

{

x[i].clear();x[i].insert(inf);x[i].insert(-inf);

y[i].clear();y[i].insert(inf);y[i].insert(-inf);

}

for(int i=1;i<=n;i++)

{

x1[i]=d[0][2*i-1]=read();ya[i]=d[1][2*i-1]=read();

x2[i]=d[0][2*i]=read();y2[i]=d[1][2*i]=read();

if(x1[i]>x2[i])swap(x1[i],x2[i]);

if(ya[i]>y2[i])swap(ya[i],y2[i]);

}

d[0][2*n+1]=xs;d[0][2*n+2]=xt;d[1][2*n+1]=ys;d[1][2*n+2]=yt;

sort(d[0]+1,d[0]+2*n+3);sort(d[1]+1,d[1]+2*n+3);

for(int i=1;i<=n;i++)

{

x1[i]=find(0,x1[i]),x2[i]=find(0,x2[i]);

ya[i]=find(1,ya[i]),y2[i]=find(1,y2[i]);

++s;

b[s].y=ya[i];b[s].x1=x1[i];b[s].x2=x2[i];

a[s].x=x1[i];a[s].ya=ya[i];a[s].y2=y2[i];

++s;

b[s].y=y2[i];b[s].x1=x1[i];b[s].x2=x2[i];

a[s].x=x2[i];a[s].ya=ya[i];a[s].y2=y2[i];

put(x1[i],ya[i]);put(x2[i],y2[i]);

put(x1[i],y2[i]);put(x2[i],ya[i]);

}

buildmap();

xs=find(0,xs);xt=find(0,xt);ys=find(1,ys);yt=find(1,yt);

solve(xs,ys,0);solve(xt,yt,1);

st=mark[xs][ys];ed=mark[xt][yt];

if(!st||!ed){puts("No Path");continue;}

dijkstra();

if(dis[ed]!=llinf)printf("%lld\n",dis[ed]);

else puts("No Path");

}

return 0;

}

« 「NOIP模拟赛」欢乐斗牛「BZOJ2346」[Baltic 2011] Lamp »

hzwer.com _ Home | http://hzwer.com

「BZOJ2304」[APIO2011] 寻路path

Description

Input

Output

Sample Input

Sample Output

题解

分类目录

热门文章

Myfriends

近期评论