# Untitled

unknown
plain_text
a year ago
1.3 kB
7
Indexable
Never
```#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define pii pair<int, int>
vector<int> dp;  // dp[i]= min cost to reach b from city i ;

int dist(pii a , pii b ){
return abs(a.first-b.first)+ abs(a.second - b.second);
}

int solve(int city , vector<int>&vis , int b, int k  ,vector<pii>town ){
if(city <=k and b <=k)return 0;
if(city==b)return 0;
if(dp[city]!=-1)return dp[city];
vis[city]=1;
int mincost = INT_MAX;
for(int i=1; i<town.size()+1 ;i++){
if(vis[i]==0){
int cost = dist(town[i-1],town[b-1])+ solve(i,vis,b,k,town );
vis[i]=0;
mincost = min(mincost , cost);
}
}

return dp[city]= mincost ;

}

int32_t main() {
int t;
cin >> t;
while (t--) {
int n, k, a, b;
cin >> n >> k >> a >> b;
dp.resize(n+1 ,-1);  // i -> city number from 1 to n
vector<int>vis(n+1,0);  // i->city number
vector<pii> city;
for (int i = 0; i < n; i++) {
int x, y;
cin >> x >> y;
city.push_back({x, y});
}
int result =0;
result = solve(a, vis ,b, k, city );
cout << result << endl;
}

return 0;
}

```