4893. 【NOIP2016提高A组集训第15场11.14】过河

Description

Input

Output

Sample Input

3
11 4 13
19 10
8 7
11 4
26 1
4 2
15 4
19 4
1 9
4 6
19 5
15 10
2 1
3 100
4 10000
5 1000000
11 4 13
19 10
8 7
11 4
26 1
4 2
15 4
19 4
1 9
4 6
19 5
15 10
2 1
3 2
4 3
5 4
1 1 1000000000
0 500000000
1 1

Sample Output

206
5
impossible

Data Constraint

Hint

Solution

 

 

 主要思想是利用边权的差值，将边数缩小，对于每一个点由半径从小到大连一条费用差值的边来表示用了更大的一个圆。

Code 

#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define I int
#define ll long long
#define db double
#define F(i,a,b) for(register I i=a;i<=b;i++)
#define mem(a,b) memset(a,b,sizeof a)
#define N 254
using namespace std;
I Tm,n,m,w,S,T,tp,st[N],d[3001260],v[2001260];
ll x[N],y[N],f[N*N],inf;
I t[2001260],nx[2001260],ls[N*N],tot,r,bz[N*N+2];
struct node{I r,v;}c[N];
inline void R(I &x){
	char c; while(!((c=getchar())>='0'&&c<='9'));
	x=c-'0';
	while((c=getchar())>='0'&&c<='9') (x*=10)+=c-'0';
}
inline I cmp(node a,node b){return a.r<b.r;}
inline db dis(I i,I j){return 1.0*sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));}
inline void add(I x,I y,I z){t[++tot]=y,nx[tot]=ls[x],ls[x]=tot;v[tot]=z;}
I main(){
	freopen("river.in","r",stdin);
	freopen("river.out","w",stdout);
	R(Tm);
	while(Tm--){
		R(n),R(m),R(w);
		mem(ls,0);tot=tp=0;
		F(i,1,n){R(S),R(T);x[i]=S,y[i]=T;}
		F(i,1,m){R(c[i].r),R(c[i].v);}
		sort(c+1,c+1+m,cmp);
		F(i,1,n){
			while(tp&&c[i].v<=c[st[tp]].v) tp--;
			st[++tp]=i;
		}
		m=tp;
		F(i,1,m) c[i]=node{c[st[i]].r,c[st[i]].v};
		F(i,1,n){
			F(j,1,n) if(i!=j){
				db ds=dis(i,j);I l=m+1;
				F(k,1,m){
					while(l>1&&ds<=c[k].r+c[l-1].r) l--;
					if(l<=m) add((i-1)*m+k,(j-1)*m+l,c[l].v);
				}
			}
		}
		F(i,1,n){
			F(j,1,m-1) add((i-1)*m+j,(i-1)*m+j+1,c[j+1].v-c[j].v);
		}
		S=n*m+1,T=n*m+2;
		F(i,1,n){
			F(j,1,m){
				if(y[i]+c[j].r>=w) add((i-1)*m+j,T,0);
				if(y[i]-c[j].r<=0) add(S,(i-1)*m+j,c[j].v);
			}
		}
		mem(f,127);inf=f[0];
		f[d[r=1]=S]=0;
		F(i,1,r){
			if(f[d[i]]>=f[d[r]]) swap(d[i],d[r]);
			I x=d[i];bz[x]=0;
			for(I k=ls[x];k;k=nx[k]) if(f[t[k]]>f[x]+v[k]){
				f[t[k]]=f[x]+v[k];
				if(!bz[t[k]]) bz[d[++r]=t[k]]=1;
			}
		}
		if(f[T]==inf) printf("impossible\n");
		else printf("%lld\n",f[T]);
	}
	return 0;
}