Advertisement
Josif_tepe

Untitled

Sep 13th, 2021
191
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.91 KB | None | 0 0
  1. #include <iostream>
  2. #include <cmath>
  3. #include <vector>
  4. #include <algorithm>
  5. #include <queue>
  6. using namespace  std;
  7. struct node{
  8.     int index;
  9.     double shortest_path;
  10.  
  11.    node(int i, double p){
  12.        index = i;
  13.        shortest_path = p;
  14.    }
  15.    bool  operator < (const node & tmp)const {
  16.            return shortest_path > tmp.shortest_path;
  17.    }
  18. };
  19. int main() {
  20.    int N;
  21.    cin >> N;
  22.    vector<pair<int,int>> kordinati;
  23.    for (int i = 0; i < N; i++) {
  24.        int a,b;
  25.        cin >> a >> b;
  26.        kordinati.push_back(make_pair(a,b));
  27.    }
  28.    vector<pair<int,double>> graph [N];
  29.    for (int i = 0; i < N; i++) {
  30.        for (int j = 0; j < N; j++) {
  31.            double D = sqrt((kordinati[j].first - kordinati[i].first) * (kordinati[j].first - kordinati[i].first) +
  32.                            (kordinati[j].second - kordinati[i].second) * (kordinati[j].second - kordinati[i].second));
  33.            if (D<=10){
  34.                graph[i].push_back(make_pair(j,D));
  35.                graph[j].push_back(make_pair(i,D));
  36.            }
  37.          }
  38.        }
  39.    priority_queue<node> pq;
  40.    pq.push(node(0,0));
  41.  
  42.    vector<bool> vistited (N+1, false);
  43.     vector<double> distance(N + 1, 2e9);
  44.     distance[0] = 0;
  45.    while (!pq.empty()){
  46.        node current = pq.top();
  47.        pq.pop();
  48.      
  49.        vistited[current.index] = true;
  50.      
  51.        if(current.index == N-1){
  52.            cout << current.shortest_path << endl;
  53.            break;
  54.        }
  55.        for (int i = 0; i < graph[current.index].size(); i++) {
  56.            int sosed = graph[current.index][i].first;
  57.            double path = graph[current.index][i].second;
  58.          
  59.            if(!vistited[sosed] and current.shortest_path + path < distance[sosed]){
  60.                pq.push(node(sosed,current.shortest_path + path));
  61.                distance[sosed] = current.shortest_path + path;
  62.            }
  63.        }
  64.      
  65.    }
  66.     return 0;
  67. }
  68.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement