牛客国庆集训派对Day1 L-New Game!（解析几何之最短路dijkstra）

思路来源

https://www.nowcoder.com/acm/contest/view-submission?submissionId=35704244

题意

n个圆，两条平行线，走在线上和圆上不花费，

问从一条平行线到另一条平行线的最小花费。

花费，将其定义为两点的欧几里得距离。

题解

将两条平行线分别抽象为2个点，

将n个圆也抽象为n个点，

然后跑一遍（n+2）个点的dijkstra或spfa就好了。

这里以0点为一条直线，(n+1)点为一条直线，中间的标号为圆抽象的点。

心得

可能还是做题比较少，思路不够灵活。

同时认识到，一道题把题解看懂，和自己真正手敲出来A掉的差距有多大...

Debug了好久...

题中也应注意一些细节，这里采用dijkstra。

①无法赋初值INF，需要循环赋double初始最大值

②n个圆之间需要两两连边，两条直线需要向所有圆连边，两条直线之间需要连边，无向图。

③计算几何求距离的部分细节操作。

代码

#include <iostream>
#include <algorithm> 
#include <cstring>
#include <cstdio>
#include <cmath>
#include <set>
#include <map>
#include <vector>
#include <stack>
#include <queue>
#include <functional>
const double INF=0x3f3f3f3f;
const int maxn=1e5+10; 
const int mod=1e9+7;
const int MOD=998244353;
const double eps=1e-7;
typedef long long ll;
#define vi vector<int> 
#define si set<int>
#define pii pair<double,int> 
#define pi acos(-1.0)
#define pb push_back
#define mp make_pair
#define lowbit(x) (x&(-x))
#define sci(x) scanf("%d",&(x))
#define scll(x) scanf("%lld",&(x))
#define sclf(x) scanf("%lf",&(x))
#define pri(x) printf("%d",(x))
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define mem(a,b) memset(a,b,sizeof(a)) 
using namespace std;
int head[1005],cnt,n,a,b,c1,c2,vis[1005];
double dis[1005];
struct edge{int to,nex;double w;}e[1<<20];
struct line{int a,b,c;}l[3];
struct circle{int x,y,r;}c[1005];
priority_queue<pii,vector<pii>,greater<pii> >q;
void init()
{
	for(int i=0;i<=n+1;++i)dis[i]=2147483644;
	cnt=0;
	mem(head,-1);
	mem(e,0);
	mem(l,0);
	mem(c,0);
	mem(vis,0);
}
double disC(circle a,circle b)
{
	double d=sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
	if(d<a.r+b.r+eps)return 0;
	return d-(a.r+b.r);
}
double disL(circle a,line b)
{
    double d=fabs(b.a*a.x+b.b*a.y+b.c)/sqrt(b.a*b.a+b.b*b.b);
	if(d<a.r+eps)return 0;
	return d-a.r; 	
}
void add(int u,int v,double w)
{
	e[cnt].to=v;
	e[cnt].w=w;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
void dijkstra(int u)
{
	while(!q.empty())q.pop(); 
	for(int j=head[u];~j;j=e[j].nex)
	{
		int v=e[j].to;
		double w=e[j].w;
		dis[v]=w;
		q.push(pii(dis[v],v));
		//printf("v:%d %lf\n",v,dis[v]);
	}
	dis[u]=0;vis[u]=1;
	while(!q.empty())
	{
		pii tmp=q.top();
		q.pop();
		int pos=tmp.second;
		double d=tmp.first;
		//printf("pos:%d\n",pos); 
		if(vis[pos])continue;
		vis[pos]=1;
		for(int i=head[pos];~i;i=e[i].nex)
		{
			int v=e[i].to;
			double w=e[i].w;
		    if(dis[v]>dis[pos]+w)
		    {
		    dis[v]=dis[pos]+w;
		    q.push(pii(dis[v],v));
		    }
		}
    }
}
int main()
{
	init();
	scanf("%d%d%d%d%d",&n,&a,&b,&c1,&c2);
	rep(j,0,1)l[j].a=a,l[j].b=b;
	l[0].c=c1,l[1].c=c2;
	rep(i,1,n)scanf("%d%d%d",&c[i].x,&c[i].y,&c[i].r);
	rep(i,1,n)
	{
		rep(j,i+1,n)
		{
			double t=disC(c[i],c[j]);
			//printf("c[%d]<->c[%d]=%lf\n",i,j,t);
			add(i,j,t);
			add(j,i,t);
		}
	}
	 rep(i,1,n)
	 {
		double p=disL(c[i],l[0]);
		add(i,0,p);
		add(0,i,p);
		double q=disL(c[i],l[1]);
		add(i,n+1,q);
		add(n+1,i,q);
	 }
    double p=fabs(l[0].c-l[1].c)/sqrt(l[0].a*l[0].a+l[0].b*l[0].b);
    add(n+1,0,p);
    add(0,n+1,p);
	dijkstra(0);
	printf("%.6lf\n",dis[n+1]); 
	return 0;
}