素晴らしき日々

1
## 4. **复杂度分析**
2

3
- **时间复杂度**：详细分析每个步骤的时间开销
4

5
- **空间复杂度**：分析内存使用情况
6

7
- **实际性能**：预估在实际数据规模下的表现
8

9
### 复杂度分析:
10
-  时间复杂度
11
  - 创图: $O(n^2)$, dijk :$O(n \log n^2)$
12
  - 总体控制在 $O(n^2),n \leq 1000$ 能够实现
13

14
-  空间复杂度
15
  - 创图: $O(n^2)$
16

17
## 5. **代码实现**
18
``` cpp
19
#include <bits/stdc++.h>
20
using namespace std;
21

22
#define int long long
23
#define x first
24
#define y second
25

26
const int N = 1e3 + 10;
27

28
using PDI = pair<double, int>;
29
int v1, v2, n;
30
class Point{
31
public:
32
  int x, y, id;
33
  double operator -(const Point &t) const{
34
      double dist = sqrt((x - t.x) * (x - t.x) + (y - t.y) * (y - t.y));
35
      if(id == n || id == 1){
36
          return dist / v1;
37
      }
38
      if(v2 * 3 >= dist) {
39
          return dist / v2;
40
      }
41
      return (dist - v2 * 3) / v1 + 3;
42
  }
43
  friend istream& operator>>(istream &in,Point& t);
44
};
45

46
istream& operator>>(istream &in,Point& t){
47
  in >> t.x >> t.y;
48
  return in;
49
}
50

51
Point p[N];
52
int h[N], ne[N * N * 2], e[N * N * 2],idx;
53
double w[N * N * 2],dist[N];
54
int st[N];
55

56
void add(int a, int b){
57
  e[idx] = b, w[idx] = p[a] - p[b], ne[idx] = h[a], h[a] = idx++;
58
}
59

60
void dijk(){
61
  for(int i = 1; i <= n; i++) dist[i] = 1e9;
62
  dist[1] = 0;
63
  priority_queue<PDI,vector<PDI>,greater<PDI>> heap;
64
  heap.push({0, 1});
65

66
  while(heap.size()){
67
      auto t = heap.top();
68
      heap.pop();
69
      int ver = t.y;
70
      double dis = t.x;
71
      if(st[ver]) continue;
72
      st[ver] = 1;
73
      for(int i = h[ver]; ~i; i = ne[i]){
74
          int j = e[i];
75
          if(dist[j] > dis + w[i]){
76
              dist[j] = dis + w[i];
77
              //cout << dist[j] << " " << ver << " " << j << endl;
78
              heap.push({dist[j], j});
79
          }
80
      }
81
  }
82
  cout << fixed << setprecision(12) << dist[n] << endl;
83
}
84

85
void solve(){
86
  cin >> n;
87
  n++;
88
  memset(h, -1, sizeof h);
89
  for(int i = 2; i <= n; i++) cin >> p[i],p[i].id = i;
90
  n++;
91
  cin >> p[1] >> p[n];
92
  p[1].id = 1, p[n].id = n;
93
  cin >> v1 >> v2;
94
  for(int i = 1; i <= n; i++){
95
      for(int j = i + 1; j <= n; j++){
96
          add(i, j), add(j, i);
97
      }
98
  }
99
  dijk();
100

101
}
102

103
signed main(){
104
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
105
  int _ = 1;
106
  //cin >> _;
107
  while(_--){
108
      solve();
109
  }
110
}