Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <queue>
- #include <cmath>
- using namespace std;
- struct node
- {
- int idx;
- double dis;
- node(int _idx, double _dis)
- {
- idx=_idx;
- dis=_dis;
- }
- bool operator < (const node &tmp) const
- {
- return dis> tmp.dis;
- }
- };
- int main()
- {
- int n,x,y;
- cin>>n;
- vector<pair<int,int>>v;
- vector<pair<int,double>>par[n+5];
- for(int i=0;i<n;i++)
- {
- cin>>x>>y;
- v.push_back({x,y});
- }
- for(int i=0;i<n;i++)
- {
- for(int j=0;j<n;j++)
- {
- 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));
- if(d <= 10)
- {
- par[i].push_back({j,d});
- }
- }
- }
- priority_queue<node>Q;
- Q.push(node(0,0));
- double d[n+5];
- bool vis[n];
- for(int j=0;j<n;j++)
- {
- d[j]=2e9;
- vis[j]=false;
- }
- d[0]=0;
- while(!Q.empty())
- {
- node teme=Q.top();
- Q.pop();
- vis[teme.idx]=true;
- for(int i=0;i<par[teme.idx].size();i++)
- {
- int sosed=par[teme.idx][i].first;
- double r=par[teme.idx][i].second;
- if(!vis[sosed] && teme.dis + r < d[sosed])
- {
- d[sosed]=teme.dis + r;
- Q.push(node(sosed,d[sosed]));
- }
- }
- }
- cout<<d[n-1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement