15686 치킨 배달

최대 50*50맵에 최대 13개의 치킨집이 있고 배달해야할 곳이 최대 2N개 있을 때

M개의 치킨집에서 집까지의 거리의 합이 최소가 되도록 골랐을 때 그 최소값을 출력하는 문제다.

1<=M<=13 이므로 경우의 수가 2^13개 밖에 되질 않는다.

집은 찾는대로 저장해놓고 순열 돌아가면서 각 집까지의 거리의 합을 구하면서 최소값을 갱신하면 된다.

아래 코드에서는 dis[치킨집][집] 을 미리 구해놓고 했는데 저러지 말고 dis[치킨집] = 집까지의 거리 총합

을 하면 더 빠를 것이다. 왜 저거 짤땐 그 생각을 못했을까.

#include <stdio.h>
#include <algorithm>
using namespace std;
 
inline int ctz(int a) {
    int r = 0;
    while (!(a & 1)) a >>= 1, r++;
    return r;
}
 
int main() {
    int n, m, a[50][50], ans = 2e9;
    int cx[13], cy[13], px[101], py[101], c_idx = 0, p_idx = 0;
    int dis[101][13];
 
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
        scanf("%d", &a[i][j]);
        if (a[i][j] == 2) cx[c_idx] = i, cy[c_idx++] = j;
        if (a[i][j] == 1) px[p_idx] = i, py[p_idx++] = j;
    }
 
    int p = (1 << m) - 1;
    int maxp = (1 << c_idx) - 1;
 
    for (int i = 0; i < p_idx; i++) for (int j = 0; j < c_idx; j++)
        dis[i][j] = abs(cx[j] - px[i]) + abs(cy[j] - py[i]);
 
    while (p <= maxp) {
        int sum = 0;
        for (int i = 0; i < p_idx; i++) {
            int mv = 150;
            for (int j = 0, bm = 1; bm <= p; j++, bm <<= 1) if (p&bm)
                mv = min(mv, dis[i][j]);
            sum += mv;
            if (sum >= ans) break;
        }
        ans = min(ans, sum);
        int t = p | (p - 1);
        p = (t + 1) | (((~t&-~t) - 1) >> (ctz(p) + 1));
    }
    printf("%d\n", ans);
    return 0;
}