Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- #include <algorithm>
- #include <utility>
- #include <cmath>
- using namespace std;
- long long int g[1000][1000];
- int d[1000];
- int main(){
- int n; cin >> n;
- vector <pair<long int, long int> > city(n);
- for (int i = 0; i < n; i++){
- cin >> city[i].first >> city[i].second;
- }
- long long int k; cin >> k;
- for (int i = 0; i < n-1; i++){
- for (int j = i+1; j < n; j++){
- if (abs(city[i].first - city[j].first) + abs(city[i].second - city[j].second) <= k){
- g[i][j] = 1;
- g[j][i] = 1;
- }
- else{
- g[i][j] = 2147483647;
- g[j][i] = 2147483647;
- }
- }
- }
- for (int i = 0; i < n; i++){
- g[i][i] = 0;
- }
- int s,f; cin >> s >> f;
- s--; f--;
- long long int c[10000];
- bool set[10000] = { false };
- set[s] = true;
- for (int i = 0; i < n; i++)
- c[i] = 2147483647;
- c[s] = 0;
- for (int i = 1; i < n; i++)
- {
- long long int min = 2147483647, m_ind;
- for (int j = 0; j < n; j++)
- if (g[s][j] >= 0 && !set[j] && s != j)
- if (c[s] + g[s][j] < c[j])
- {
- c[j] = c[s] + g[s][j];
- if (c[j] < min)
- {
- min = c[j];
- m_ind = j;
- }
- }
- s = m_ind;
- }
- if (c[f] == 2147483647)
- cout << -1;
- else
- cout << c[f];
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement