Advertisement
Guest User

Untitled

a guest
Jan 20th, 2020
61
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.89 KB | None | 0 0
  1. #include <iostream>
  2. #include <math.h>
  3. #include <cmath>
  4. #include <algorithm>
  5. #include <iomanip>
  6. #include <queue>
  7. #include <stack>
  8. #include <climits>
  9.  
  10. using namespace std;
  11.  
  12. long n, m;
  13. struct ostrov {
  14.    long x, y, r;
  15. };
  16.  
  17.  
  18. void dk(vector <vector<long>> mas, long a, long b) {
  19.     vector <bool> used(n);
  20.     vector <double> l(n, INT_MAX);
  21.    
  22.     l[a] = 0;
  23.     for (long i = 0; i < n; i++)
  24.     {
  25.         long min = INT_MAX;
  26.         long s = INT_MIN;
  27.         for (int j = 0; j < n; j++)
  28.         {
  29.             if (!used[j] && l[j] < min) {
  30.                 min = l[j];
  31.                 s = j;
  32.             }
  33.         }
  34.         if (s == INT_MIN) break;
  35.        
  36.         for (long j = 0; j < n; j++) {
  37.             if (!used[j] && mas[s][j] != -1) {
  38.                 if (l[s] + mas[s][j] < l[j])  l[j] = l[s] + mas[s][j];
  39.             }
  40.         }
  41.         used[s] = true;
  42.     }
  43.     if (l[b] != INT_MAX) {
  44.         printf("%.5f", l[b]); cout << endl;
  45.     }
  46.    
  47.     else cout << "-1";
  48.    
  49. }
  50.  
  51.  
  52. int main() {
  53.    // freopen("input.txt", "r", stdin);
  54.    // freopen("output.txt", "w", stdout);
  55.     long a, b;
  56.  
  57.     cin >> n;
  58.     vector <vector<long>> mas(n);
  59.     for (long i = 0; i < n; i++) {
  60.         mas[i].resize(n);
  61.  
  62.     }
  63.    
  64.     vector <ostrov> ostrov1;
  65.     ostrov1.resize(n);
  66.     for (long i = 0; i < n; i++) {
  67.         cin >> ostrov1[i].x;
  68.         cin >> ostrov1[i].y;
  69.         cin >> ostrov1[i].r;
  70.     }
  71.     for (long i = 0; i < n; i++) {
  72.         for (long j = i + 1; j < n; j++) {
  73.  
  74.             mas[i][j]= mas[j][i]  = sqrt(abs(ostrov1[i].x - ostrov1[j].x)* abs(ostrov1[i].x - ostrov1[j].x)
  75.                 + abs(ostrov1[i].y - ostrov1[j].y)* abs(ostrov1[i].y - ostrov1[j].y))
  76.                 - ostrov1[i].r - ostrov1[j].r;
  77.         }
  78.     }
  79.  
  80.     cin >> m;
  81.     for (long i = 0; i < m; i++)
  82.     {
  83.         cin >> a >> b;
  84.         a--; b--;
  85.         dk(mas,a,b);
  86.     }
  87. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement