Advertisement
ivangarvanliev

Untitled

Feb 8th, 2025
60
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.93 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <queue>
  4. #include <cmath>
  5. using namespace std;
  6.  
  7. const int INF = 1e9;
  8. int N;
  9. vector<pair<int, int>> systems;
  10. vector<vector<pair<int, double>>> graph;
  11.  
  12. double euclidean_distance(pair<int, int> A, pair<int, int> B) {
  13.     double dx = A.first - B.first;
  14.     double dy = A.second - B.second;
  15.     return sqrt(dx * dx + dy * dy);
  16. }
  17. void create_graph() {
  18.     graph.resize(N);
  19.     for (int i = 0; i < N; i++) {
  20.         for (int j = 0; j < N; j++) {
  21.             if (i != j) {
  22.                 double weight = euclidean_distance(systems[i], systems[j]);
  23.                 if (weight <= 10) {
  24.                     graph[i].push_back({j, weight});
  25.                     graph[j].push_back({i, weight});
  26.                 }
  27.             }
  28.         }
  29.     }
  30. }
  31.  
  32.  
  33. vector<double> dijkstra(int start) {
  34.     vector<double> dist(N, INF);
  35.     priority_queue<pair<double, int>, vector<pair<double, int>>, greater<pair<double, int>>> pq;
  36.      
  37.     dist[start] = 0;
  38.     pq.push({0, start});
  39.      
  40.     while (!pq.empty()) {
  41.         int node = pq.top().second;
  42.         double curr_dist = pq.top().first;
  43.         pq.pop();
  44.          
  45.         if (curr_dist > dist[node]) continue;
  46.          
  47.         for (auto &edge : graph[node]) {
  48.             int neighbor = edge.first;
  49.             double weight = edge.second;
  50.              
  51.             if (dist[node] + weight < dist[neighbor]) {
  52.                 dist[neighbor] = dist[node] + weight;
  53.                 pq.push({dist[neighbor], neighbor});
  54.             }
  55.         }
  56.     }
  57.     return dist;
  58. }
  59.  
  60. int main() {
  61.     cin >> N;
  62.     systems.resize(N);
  63.      
  64.     for (int i = 0; i < N; i++) {
  65.         cin >> systems[i].first >> systems[i].second;
  66.     }
  67.      
  68.     create_graph();
  69.      
  70.     vector<double> distances = dijkstra(0);
  71.     double result = distances[N - 1];
  72.      
  73.     cout.precision(10);
  74.     cout << fixed << result << endl;
  75.      
  76.     return 0;
  77. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement