TOI12: Pipe

#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 ;
using pii=pair<int,int>;
int distance(pii a,pii b ){
    return abs(a.first-b.first) + abs(a.second-b.second);
}
int main(){

    int n,k;
    scanf("%d%d",&n,&k);
    pii point[n+1];
    int dis[n+1],idx[n+1];
    bool visited[n+1];

    for(int i=1;i<=n;i++){
        int x,y;
        visited[i]=false;
        dis[i]=INF;
        idx[i]=i;
        scanf("%d%d",&point[i].first,&point[i].second);
    }

    int cnt=n,dist=0,u=1,d=0,I=1;
    dis[1]=0;
    while(cnt>0){

        dist+=d;
        swap(idx[I],idx[cnt]);
        cnt--;
        int U=u;
        d=INF;

        for(int v=1;v<=cnt;v++){
            int w=distance(point[U],point[idx[v]]);
            if(w<dis[idx[v]]){
                dis[idx[v]]=w;
            }
            if(dis[ idx[v] ]<d){
                d=dis[ idx[v] ];
                u=idx[v];
                I=v;
            }
        }
    }

    sort(dis+1,dis+n+1,greater<int>());
    for(int i=1;i<=k-1;i++){
        dist-=dis[i];
    }
    printf("%d",dist);

    return 0;
}