시작 위치를 0번 노드, 모든 대포를 1~N, 목적지를 N+1번 노드로 한다. 각각의 노드끼리 이동하는데 걸리는 시간을 모두 (N+1)*(N+1)배열에 기록한다.
30m보다 거리가 짧은 경우 그냥 걸어가는게 이득이고, 30m보다 거리가 긴 경우 대포를 타고 남은 거리만 걸어가는게 이득이다. 시작점에서는 대포를 탈 수 없다는 점을 주의하자.
해당 규칙에 따라 걸리는 시간을 기록하고, 다익스트라를 돌려주면 끝이다.
#include <bits/stdc++.h>
using namespace std;
constexpr double INF = 2e9;
vector<pair<double, double>> cannon;
pair<double, double> start, dest;
int N;
double table[102][102];
double time_s[102];
bool visited[102];
double get_dist(pair<double, double> p1, pair<double, double> p2) {
return sqrt(pow(p1.first-p2.first, 2)+pow(p1.second-p2.second, 2));
}
void dijkstra() {
priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
pq.push({0, 0});
for (int i = 1; i <= N+1; i++) {
time_s[i] = INF;
}
while (!pq.empty()) {
double cost = pq.top().first;
int cur = pq.top().second;
pq.pop();
if (visited[cur]) continue;
visited[cur] = true;
for (int i = 0; i <= N+1; i++) {
if (cur == i || visited[i]) continue;
if (time_s[i] > time_s[cur] + table[cur][i]) {
time_s[i] = time_s[cur] + table[cur][i];
pq.push({cost+table[cur][i], i});
}
}
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout << fixed;
cout.precision(4);
cin >> start.first >> start.second;
cin >> dest.first >> dest.second;
cin >> N;
cannon = vector<pair<double, double>>(N);
for (int i = 0; i < N; i++) {
cin >> cannon[i].first >> cannon[i].second;
}
double d = get_dist(start, dest);
table[0][N+1] = d/5;
table[N+1][0] = table[0][N+1];
for (int i = 0; i < N; i++) {
d = get_dist(start, cannon[i]);
table[0][i+1] = d/5;
table[i+1][0] = table[0][i+1];
}
for (int i = 0; i < N; i++) {
d = get_dist(dest, cannon[i]);
table[N+1][i+1] = d > 30 ? abs(50-d)/5 + 2 : d/5;
table[i+1][N+1] = table[N+1][i+1];
}
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j++) {
if (i == j) continue;
d = get_dist(cannon[i], cannon[j]);
table[i+1][j+1] = d > 30 ? abs(50-d)/5 + 2 : d/5;
table[j+1][i+1] = table[i+1][j+1];
}
}
dijkstra();
cout << time_s[N+1];
return 0;
}
기하도 싫고 소수점 다루기도 싫다.