题目链接
题意
给互相平行的直线L1,L2,和N个圆，角色在直线上、圆上、园内行走不消耗体力。在其他位置上由S点走到T点消耗的体力为S和T的欧几里得距离。求最少需要多少体力。
解题思路
这题和poj2502那题很相似，关键在建图，这里考察了圆到圆的最短距离和线到圆的最短距离，一开始写的代码以为圆内要消耗体力，然后计算了一下内含情况的最短距离，结果也AC了，后来发现不需要，可能是题目数据没这种情况吧。
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<double,int> pii;
const int maxn = 1e6+5;
const double inf = 1e30;
int n,A,B,C1,C2;
struct Edge
{
int from,to;
double val;
};
vector<Edge> G[maxn];
struct Node
{
int x,y;
double r;
};
Node C[maxn];
double getval(Node a,Node b)
{
if(a.r < b.r){
swap(a,b);
}
double len = sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
if(len > a.r + b.r){
return len - a.r - b.r;
}else{
return 0;
}
}
double dis[maxn];
bool vis[maxn];
void dijkstra()
{
memset(vis,0,sizeof(vis));
fill(dis,dis+maxn,inf);
dis[n] = 0;
priority_queue<pii,vector<pii>,greater<pii> > Q;
Q.push(pii(0,n));
while(!Q.empty()){
pii t = Q.top();
Q.pop();
double d = t.first;
int u = t.second;
if(vis[u])continue;
vis[u] = 1;
for(int i=0;i<G[u].size();i++){
Edge e = G[u][i];
if(e.val + d < dis[e.to]){
dis[e.to] = e.val + d;
Q.push(pii(dis[e.to],e.to));
}
}
}
cout << dis[n+1]<< endl;
}
int main(int argc, char const *argv[])
{
cin >> n >> A >> B >> C1 >> C2;
for(int i=0;i<n;i++){
cin >> C[i].x >> C[i].y >> C[i].r;
}
Edge e;
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
if(i==j)continue;
e.from = i;
e.to = j;
e.val = getval(C[i],C[j]);
G[e.from].push_back(e);
swap(e.from,e.to);
G[e.from].push_back(e);
}
}
double di = sqrt(A*A+B*B);
for(int i=0;i<n;i++){
double t = abs(A*C[i].x + B*C[i].y + C1)/di - C[i].r;
if(t < 0) t = 0;
e.from = n;
e.to = i;
e.val = t;
G[e.from].push_back(e);
swap(e.from, e.to);
G[e.from].push_back(e);
}
for(int i=0;i<n;i++){
double t = 1.0*abs(A*C[i].x + B*C[i].y + C2)/di - C[i].r;
if(t < 0) t = 0;
e.from = n+1;
e.to = i;
e.val = t;
G[e.from].push_back(e);
swap(e.from, e.to);
G[e.from].push_back(e);
}
double t = 1.0*abs(C1-C2)/di;
e.from = n;
e.to = n+1;
e.val = t;
G[e.from].push_back(e);
swap(e.from, e.to);
G[e.from].push_back(e);
dijkstra();
return 0;
}
|
