Advertisement
Josif_tepe

Untitled

May 3rd, 2021
138
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.44 KB | None | 0 0
  1.  
  2. #include <iostream>
  3. #include <vector>
  4. #include <queue>
  5. #include <cmath>
  6. using namespace std;
  7. struct node{
  8. int index;
  9. double distance;
  10. node(){
  11.  
  12. }
  13. node(int _index, double _distance){
  14. index=_index;
  15. distance=_distance;
  16. }
  17. bool operator <(const node& temp)const{
  18. return distance>temp.distance;
  19. }
  20. };
  21.  
  22. int main()
  23. {
  24. int n;
  25. cin>>n;
  26. vector<pair<int, double>>v;
  27. vector<pair<int, double>>graph[n];
  28. for(int x=0; x<n; x++){
  29.     int a, b;
  30.     cin>>a;
  31.     cin>>b;
  32.     v.push_back(make_pair(a, b));
  33. }
  34. for(int y=0; y<v.size(); y++){
  35.     for(int u=0; u<v.size(); u++){
  36.         double d=sqrt((v[y].first-v[u].first)*(v[y].first-v[u].first)+(v[u].second-v[y].second)*(v[u].second-v[y].second));
  37.         if(d<=10){
  38.          graph[y].push_back(make_pair(u, d));
  39.         }
  40.     }
  41. }
  42. int s, e;
  43. s=0;
  44. e=n-1;
  45.     priority_queue<node>pq;
  46.     pq.push(node(s, 0));
  47.     bool visited [n];
  48.     double distance[n];
  49.     for(int h=0; h<n; h++){
  50.         visited[h]=false;
  51.         distance[h]=200000000;
  52.     }
  53.     distance[0] = 0;
  54.     while(!pq.empty()){
  55.     node c=pq.top();
  56.     pq.pop();
  57.     visited[c.index]=true;
  58.     for(int k=0; k<graph[c.index].size(); k++){
  59.     int sosed=graph[c.index][k].first;
  60.     double d1=graph[c.index][k].second;
  61.     if((visited[sosed]==false)and(c.distance+d1<distance[sosed])){
  62.      distance[sosed]=c.distance+d1;
  63.      pq.push(node(sosed, distance[sosed]));
  64.     }
  65.     }
  66.     }
  67.     cout<<distance[n-1];
  68.     return 0;
  69. }
  70.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement