-
Notifications
You must be signed in to change notification settings - Fork 1
/
boj 10473.cpp
62 lines (54 loc) · 1.7 KB
/
boj 10473.cpp
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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double INF = 2e9;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
double sy, sx, ey, ex;
cin >> sy >> sx >> ey >> ex;
int n; cin >> n;
vector<pair<double, double>> a(n + 2);
for (int i = 1; i <= n; i++) {
double y, x;
cin >> y >> x;
a[i] = {y, x};
}
a[0] = {sy, sx};
a[n + 1] = {ey, ex};
double t[n + 2][n + 2];
for (int i = 0; i < n + 2; i++) {
for (int j = 0; j < n + 2; j++) {
double y2 = (a[i].first - a[j].first) * (a[i].first - a[j].first);
double x2 = (a[i].second - a[j].second) * (a[i].second - a[j].second);
double td = sqrt(y2 + x2);
if (i == 0 || i == n + 1) t[i][j] = td / 5.0;
else t[i][j] = min(td / 5.0, abs(td - 50.0) / 5.0 + 2.0);
}
}
double time[n + 2];
bool visited[n + 2];
for (int i = 0; i < n + 2; i++) {
time[i] = INF;
visited[i] = false;
}
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> q;
time[0] = 0.0;
q.push({0.0, 0});
while (!q.empty()) {
int cur = q.top().second; q.pop();
if (visited[cur]) continue;
visited[cur] = true;
for (int i = 0; i < n + 2; i++) {
int nxt = i;
if (visited[nxt]) continue;
double w = t[cur][nxt];
if (time[cur] + w < time[nxt]) {
time[nxt] = time[cur] + w;
q.push({time[nxt], nxt});
}
}
}
cout << fixed << setprecision(6) << time[n + 1];
return 0;
}