Comet OJ 热身赛（E题）（处理+最短路算法）

<div class="problems-statistical" data-v-c91880aa=""> <div class="problems-status" data-v-c91880aa=""> <div class="title" data-v-c91880aa=""> dijkstra </div> <button class="purple" data-v-c91880aa="">已经提交</button> <button class="purple" data-v-c91880aa="">已经通过</button> </div> <div class="round" data-v-c91880aa=""> 42.86% </div> <div class="data" data-v-c91880aa=""> Total Submission：189 Total Accepted：81 </div> </div> <div class="problems-header markdown-body" data-v-c91880aa=""> 题目描述   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 。请计算最少需要多少体力。   </div> <div class="problems-header ivu-card ivu-card-dis-hover ivu-card-shadow" data-v-c91880aa=""> <div class="ivu-card-head">   </div> <div class="ivu-card-extra">   </div> <div class="ivu-card-body"> <div class="panel-body"> <div id="problem-content" class="markdown-body" data-v-c91880aa=""> 输入描述   第一行五个正整数 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 即算正确。   <div data-v-c91880aa=""> <div class="flex-container sample" data-v-c91880aa=""> <div class="sample-input" data-v-c91880aa=""> 样例输入 1  <pre data-v-c91880aa="">2 0 1 0 -4 0 1 1 1 3 1</pre> </div> <div class="sample-output" data-v-c91880aa=""> 样例输出 1 <pre data-v-c91880aa="">0.236068 题意：给定两个平行的直线，直线中间有若干个圆，点在直线和圆上行走不消耗能力。问从第一条直线走到第二条直线最小需要消耗多少能量。 距离即代表消耗的能力。 思路： 1、首先处理每一个圆心到其他圆心和直线的距离，以各个圆心点和直线缩成点构成一个图，然后根据距离跑最短路算法即可。 2、注意距离减去半径的时候如果是负数要赋值为0。 细节见我的代码； </pre> <div class="cnblogs_code"> <pre>#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=10008; 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,1,maxn-1) { dis[i]=9999999999.0; } dis[strat]=0; heap.push(Node(strat,dis[strat])); while(!heap.empty()) { Node x= heap.top(); heap.pop(); int LEN=Map[x.to].size(); rep(i,0,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,3,n+2) { gg(y[i].x); gg(y[i].y); gg(y[i].r); } repd(i,3,n+2) { double dt=max(getdis(i)-y[i].r,0.00); Map[1].push_back(Node(i,dt)); Map[i].push_back(Node(1,dt)); } repd(i,3,n+2) { double dt=max(getdis2(i)-y[i].r,0.00); Map[2].push_back(Node(i,dt)); Map[i].push_back(Node(2,dt)); } repd(i,3,n+2) { repd(j,3,n+2) { 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(1); printf("%.6lf\n",dis[2] ); return 0; } inline void getInt(int* p) { char ch; do { ch = getchar(); } while (ch == ' ' || ch == '\n'); if (ch == '-') { *p = -(getchar() - '0'); while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 - ch + '0'; } } else { *p = ch - '0'; while ((ch = getchar()) >= '0' && ch <= '9') { *p = *p * 10 + ch - '0'; } } }</pre> </div>   <pre data-v-c91880aa=""></pre> </div> </div> </div> </div> </div> </div> </div> <audio controls="controls" style="display: none;"></audio>