Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <queue>
- #include <cmath>
- using namespace std;
- struct node{
- int index;
- double distance;
- node(){
- }
- node(int _index, double _distance){
- index=_index;
- distance=_distance;
- }
- bool operator <(const node& temp)const{
- return distance>temp.distance;
- }
- };
- int main()
- {
- int n;
- cin>>n;
- vector<pair<int, double>>v;
- vector<pair<int, double>>graph[n];
- for(int x=0; x<n; x++){
- int a, b;
- cin>>a;
- cin>>b;
- v.push_back(make_pair(a, b));
- }
- for(int y=0; y<v.size(); y++){
- for(int u=0; u<v.size(); u++){
- 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));
- if(d<=10){
- graph[y].push_back(make_pair(u, d));
- }
- }
- }
- int s, e;
- s=0;
- e=n-1;
- priority_queue<node>pq;
- pq.push(node(s, 0));
- bool visited [n];
- double distance[n];
- for(int h=0; h<n; h++){
- visited[h]=false;
- distance[h]=200000000;
- }
- distance[0] = 0;
- while(!pq.empty()){
- node c=pq.top();
- pq.pop();
- visited[c.index]=true;
- for(int k=0; k<graph[c.index].size(); k++){
- int sosed=graph[c.index][k].first;
- double d1=graph[c.index][k].second;
- if((visited[sosed]==false)and(c.distance+d1<distance[sosed])){
- distance[sosed]=c.distance+d1;
- pq.push(node(sosed, distance[sosed]));
- }
- }
- }
- cout<<distance[n-1];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement