Advertisement
Josif_tepe

Untitled

Sep 12th, 2023
738
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.41 KB | None | 0 0
  1. #include <queue>
  2. #include <iostream>
  3. #include <vector>
  4. #include <cstring>
  5. #include <iostream>
  6. //#include <bits/stdc++.h>
  7. using namespace std;
  8.  
  9.  
  10.  
  11.  
  12.  
  13.  
  14. int main()
  15. {
  16.     int n;
  17.     cin>>n;
  18.     vector < pair<int,int> > v;
  19.     int x,y;
  20.     for(int i=0;i<n;i++)
  21.     {
  22.         cin>>x>>y;
  23.         v.push_back(make_pair(x,y));
  24.     }
  25.     vector < pair<int, double> > g[n];
  26.  
  27.  
  28.  
  29.  
  30.    vector<bool> visited(n,false);
  31.     vector<double> dis(n,-2e9);
  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.                 g[i].push_back(make_pair(j,-d));
  39.         }
  40.     }
  41.     dis[0]=0;
  42.     priority_queue<pair<double, int> > pq;
  43.     pq.push(make_pair(0,0));
  44.  
  45.  
  46.  
  47.  
  48.    while(!pq.empty())
  49.     {
  50.         pair<double, int> c=pq.top();
  51.  
  52.         pq.pop();
  53.  
  54.  
  55.        if(visited[c.second])
  56.         {
  57.             continue;
  58.         }
  59.         visited[c.second]=true;
  60.         for(int i=0;i<g[c.second].size();i++)
  61.         {
  62.             int s=g[c.second][i].first;
  63.             double t=g[c.second][i].second;
  64.  
  65.  
  66.  
  67.  
  68.            if(!visited[s] && c.first+t>dis[s])
  69.             {
  70.                 pq.push(make_pair(c.first+t, s));
  71.                 dis[s]=c.first+t;
  72.             }
  73.         }
  74.     }
  75.     cout<<-dis[n-1]<<endl;
  76.     return 0;
  77. }
  78.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement