bzoj3007 拯救小云公主

Description

Input

Output

Sample Input

Sample Output

HINT

思路不错的一道题。

任意两个圆之间连边，长度为圆心距的一半。然后问题转化为，从左上两条边到右下两条边找一条路径，使得路径上的最大边最小，SPFA。

注意ans的初值是圆心到起点和终点距离的最小值。(详见程序)

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#define F(i,j,n) for(int i=j;i<=n;i++)
#define D(i,j,n) for(int i=j;i>=n;i--)
#define ll long long
#define maxn 3005
using namespace std;
int n,nx,ny,s,t;
double ans,dis[maxn],g[maxn][maxn];
bool inq[maxn];
struct data{int x,y;}a[maxn];
const double inf=1e10;
queue<int> q;
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;
}
inline double getdis(data a,data b)
{
	double x=a.x-b.x,y=a.y-b.y;
	return sqrt(x*x+y*y);
}
inline void spfa()
{
	F(i,1,t) dis[i]=inf;
	dis[s]=0;inq[s]=true;q.push(s);
	while (!q.empty())
	{
		int x=q.front();q.pop();inq[x]=false;
		F(i,1,t) if (x!=i&&max(dis[x],g[x][i])<dis[i])
		{
			dis[i]=max(dis[x],g[x][i]);
			if (!inq[i]) inq[i]=true,q.push(i);
		}
	}
}
int main()
{
	n=read();nx=read();ny=read();
	s=n+1;t=n+2;
	F(i,1,n) a[i].x=read(),a[i].y=read();
	F(i,1,n) g[s][i]=g[i][s]=min(a[i].x-1,ny-a[i].y),g[i][t]=g[t][i]=min(a[i].y-1,nx-a[i].x);
	F(i,1,n) F(j,i,n) g[i][j]=g[j][i]=getdis(a[i],a[j])/2;
	ans=inf;
	F(i,1,n) ans=min(ans,getdis(a[i],(data){1,1})),ans=min(ans,getdis(a[i],(data){nx,ny}));
	g[s][t]=g[t][s]=min(nx-1,ny-1);
	spfa();
	ans=min(ans,dis[t]);
	printf("%.2lf\n",ans);
}

bzoj3007 拯救小云公主

原文：http://blog.csdn.net/aarongzk/article/details/51138637