dijkstra
已经提交 已经通过
42.86%
Total Submission：189
Total Accepted：81
题目描述
Eagle Jump公司正在开发一款新的游戏。泷本一二三作为其员工，获得了提前试玩的机会。现在她正在试图通过一个迷宫。
这个迷宫有一些特点。为了方便描述，我们对这个迷宫建立平面直角坐标系。迷宫中有两条平行直线 L_1:Ax+By+C_1=0L1:Ax+By+C1=0, L_2:Ax+By+C_2=0L2:Ax+By+C2=0，还有 nn 个圆 C_i:(x-x_i)^2+(y-y_i)^2={r_i}^2Ci:(x−xi)2+(y−yi)2=ri2。角色在直线上、圆上、圆内行走不消耗体力。在其他位置上由SS点走到TT点消耗的体力为SS和TT的欧几里得距离。
泷本一二三想从 L_1L1 出发，走到 L_2L2 。请计算最少需要多少体力。
输入描述
第一行五个正整数 n,A,B,C_1,C_2n,A,B,C1,C2 (1\le n \le 1000, -10000 \le A,B,C_1,C_2 \le 10000)(1≤n≤1000,−10000≤A,B,C1,C2≤10000)，其中 A,BA,B 不同时为 0。
接下来 nn 行每行三个整数 x,y,r(-10000 \le x,y \le 10000, 1\le r \le 10000)x,y,r(−10000≤x,y≤10000,1≤r≤10000) 表示一个圆心为 (x,y)(x,y)，半径为 rr 的圆。
输出描述
仅一行一个实数表示答案。与标准答案的绝对误差或者相对误差不超过 10^{-4}10−4 即算正确。
样例输入 1
2 0 1 0 -4
0 1 1
1 3 1
样例输出 1
0.236068 题意：给定两个平行的直线，直线中间有若干个圆，点在直线和圆上行走不消耗能力。问从第一条直线走到第二条直线最小需要消耗多少能量。
距离即代表消耗的能力。
思路：
1、首先处理每一个圆心到其他圆心和直线的距离，以各个圆心点和直线缩成点构成一个图，然后根据距离跑最短路算法即可。
2、注意距离减去半径的时候如果是负数要赋值为0。
细节见我的代码；
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
#include <map>
#include <set>
#include <vector>
#define rep(i,x,n) for(int i=x;i<n;i++)
#define repd(i,x,n) for(int i=x;i<=n;i++)
#define pii pair<int,int>
#define pll pair<long long ,long long>
#define gbtb std::ios::sync_with_stdio(false)
#define MS0(X) memset((X), 0, sizeof((X)))
#define MSC0(X) memset((X), '\0', sizeof((X)))
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define gg(x) getInt(&x)
using namespace std;
typedef long long ll;
inline void getInt(int* p);
/*** TEMPLATE CODE STARTS HERE ***/
const int maxn=;
const int INF= 0x3f3f3f3f;
struct Node
{
int to;
double dist;
Node(){}
Node(int _n,double _d)
{
to=_n;
dist=_d;
}
bool operator < (const Node x ) const
{
return dist > x.dist;
}
};
priority_queue<Node> heap;
vector <Node> Map[maxn];
double dis[maxn];
int t,n,star;
void dijkstra (int strat)
{
// memset(dis,INF,sizeof(dis));
repd(i,,maxn-)
{
dis[i]=9999999999.0;
}
dis[strat]=;
heap.push(Node(strat,dis[strat]));
while(!heap.empty())
{
Node x= heap.top();
heap.pop();
int LEN=Map[x.to].size();
rep(i,,LEN)
{
Node now =Map[x.to][i];
if(dis[now.to]>x.dist+now.dist)
{
dis[now.to]=x.dist+now.dist;
heap.push(Node(now.to,dis[now.to]));
}
}
} }
int a,b,c1,c2;
struct yuan
{
int x,r,y;
}y[maxn];
double getdis(int id)
{
double res=0.00000;
res=max(0.000,fabs(a*y[id].x+b*y[id].y+c1)*1.000/sqrt(a*a+b*b));
return res; }
double getdis2(int id)
{
double res=0.00000;
res=max(0.00,fabs(a*y[id].x+b*y[id].y+c2)*1.000/sqrt(a*a+b*b));
return res; }
int main()
{
// scanf("%d %d %d",&n,&t,&star);
// int a,b,d;
// repd(i,1,t)
// {
// scanf("%d %d %d",&a,&b,&d);
// Map[a].pb(Node(b,d));
// // Map[b].pb(Node(a,d));
// }
// dijkstra(star);
// printf("%d\n",ans);
gg(n);
gg(a);gg(b);gg(c1);gg(c2);
repd(i,,n+)
{
gg(y[i].x);
gg(y[i].y);
gg(y[i].r);
}
repd(i,,n+)
{
double dt=max(getdis(i)-y[i].r,0.00);
Map[].push_back(Node(i,dt));
Map[i].push_back(Node(,dt));
}
repd(i,,n+)
{
double dt=max(getdis2(i)-y[i].r,0.00);
Map[].push_back(Node(i,dt));
Map[i].push_back(Node(,dt));
}
repd(i,,n+)
{
repd(j,,n+)
{
if(i==j)
{
continue;
}else
{
double dt=max(0.000,-y[i].r-y[j].r+sqrt((y[i].x-y[j].x)*(y[i].x-y[j].x)+(y[i].y-y[j].y)*(y[i].y-y[j].y)));
Map[i].push_back(Node(j,dt));
Map[j].push_back(Node(i,dt));
}
}
}
dijkstra();
printf("%.6lf\n",dis[] );
return ;
} inline void getInt(int* p) {
char ch;
do {
ch = getchar();
} while (ch == ' ' || ch == '\n');
if (ch == '-') {
*p = -(getchar() - '');
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * - ch + '';
}
}
else {
*p = ch - '';
while ((ch = getchar()) >= '' && ch <= '') {
*p = *p * + ch - '';
}
}
}