Advertisement
Guest User

Untitled

a guest
Sep 19th, 2017
58
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.38 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <utility>
  5. #include <cmath>
  6. using namespace std;
  7. long long int g[1000][1000];
  8. int d[1000];
  9.  
  10. int main(){
  11. int n; cin >> n;
  12. vector <pair<long int, long int> > city(n);
  13. for (int i = 0; i < n; i++){
  14. cin >> city[i].first >> city[i].second;
  15. }
  16. long long int k; cin >> k;
  17.  
  18. for (int i = 0; i < n-1; i++){
  19. for (int j = i+1; j < n; j++){
  20. if (abs(city[i].first - city[j].first) + abs(city[i].second - city[j].second) <= k){
  21. g[i][j] = 1;
  22. g[j][i] = 1;
  23. }
  24. else{
  25. g[i][j] = 2147483647;
  26. g[j][i] = 2147483647;
  27. }
  28.  
  29. }
  30. }
  31. for (int i = 0; i < n; i++){
  32. g[i][i] = 0;
  33. }
  34. int s,f; cin >> s >> f;
  35. s--; f--;
  36. long long int c[10000];
  37. bool set[10000] = { false };
  38. set[s] = true;
  39. for (int i = 0; i < n; i++)
  40. c[i] = 2147483647;
  41. c[s] = 0;
  42. for (int i = 1; i < n; i++)
  43. {
  44. long long int min = 2147483647, m_ind;
  45. for (int j = 0; j < n; j++)
  46. if (g[s][j] >= 0 && !set[j] && s != j)
  47. if (c[s] + g[s][j] < c[j])
  48. {
  49. c[j] = c[s] + g[s][j];
  50. if (c[j] < min)
  51. {
  52. min = c[j];
  53. m_ind = j;
  54. }
  55. }
  56. s = m_ind;
  57. }
  58. if (c[f] == 2147483647)
  59. cout << -1;
  60. else
  61. cout << c[f];
  62. return 0;
  63. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement