15686 치킨 배달

https://www.acmicpc.net/problem/15686

치킨집 중에서 M개를 고르는 모든 조합을 만든 후 각각의 집을 가장 가까운 치킨집에 연결시킨다. 모든 경우 중 최소값이 답이다.

#include <cstdio>
#include <cmath>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
 
int n,m,t,lenh,lenc,ans=INF;
vector<pair<int,int>> h,c;
 
int dist(pair<int,int> a,pair<int,int> b)
{
    return abs(a.first-b.first)+abs(a.second-b.second);
}
 
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            scanf("%d",&t);
            if(t==1) h.push_back({i,j});
            else if(t==2) c.push_back({i,j});
        }
    }
    lenh=h.size(),lenc=c.size();
    vector<int> p(lenc,1);
    for(int i=0;i<m;i++) p[i]=0;
    do
    {
        int sum=0;
        for(int i=0;i<lenh;i++)
        {
            int minv=INF;
            for(int j=0;j<lenc;j++)
                if(!p[j]) minv=min(minv,dist(h[i],c[j]));
            sum+=minv;
        }
        ans=min(ans,sum);
    } while(next_permutation(p.begin(),p.end()));
    printf("%d\n",ans);
    return 0;
}