Advertisement
Josif_tepe

Untitled

Jan 25th, 2022
1,080
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.50 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <queue>
  5. #include <cmath>
  6. using namespace std;
  7. struct node
  8. {
  9.     int idx;
  10.     double dis;
  11.     node(int _idx, double _dis)
  12.     {
  13.         idx=_idx;
  14.         dis=_dis;
  15.     }
  16.     bool operator < (const node &tmp) const
  17.     {
  18.         return dis> tmp.dis;
  19.     }
  20. };
  21. int main()
  22. {
  23.     int n,x,y;
  24.     cin>>n;
  25.     vector<pair<int,int>>v;
  26.     vector<pair<int,double>>par[n+5];
  27.     for(int i=0;i<n;i++)
  28.     {
  29.         cin>>x>>y;
  30.         v.push_back({x,y});
  31.     }
  32.     for(int i=0;i<n;i++)
  33.     {
  34.         for(int j=0;j<n;j++)
  35.         {
  36.             double d=sqrt((v[j].first-v[i].first)*(v[j].first-v[i].first)+(v[j].second-v[i].second)*(v[j].second-v[i].second));
  37.             if(d <= 10)
  38.             {
  39.                 par[i].push_back({j,d});
  40.             }
  41.         }
  42.     }
  43.     priority_queue<node>Q;
  44.     Q.push(node(0,0));
  45.     double d[n+5];
  46.     bool vis[n];
  47.     for(int j=0;j<n;j++)
  48.     {
  49.         d[j]=2e9;
  50.         vis[j]=false;
  51.     }
  52.     d[0]=0;
  53.     while(!Q.empty())
  54.     {
  55.         node teme=Q.top();
  56.         Q.pop();
  57.         vis[teme.idx]=true;
  58.         for(int i=0;i<par[teme.idx].size();i++)
  59.         {
  60.             int sosed=par[teme.idx][i].first;
  61.             double r=par[teme.idx][i].second;
  62.             if(!vis[sosed] && teme.dis + r < d[sosed])
  63.             {
  64.                 d[sosed]=teme.dis + r;
  65.                 Q.push(node(sosed,d[sosed]));
  66.             }
  67.         }
  68.     }
  69.     cout<<d[n-1];
  70.     return 0;
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement