50112. Apartments and Friends

#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#include <ctype.h>

#define min(x,y) ((x)<(y)?(x):(y))
#define abs(x) ((x)<(0)?(-(x)):(x))

int n, m;
char friends[11][11] = {0};
char f_cnt[11] = {0};
int min_dis = INT_MAX;

void dfs(int idx[], int now_cnt, int now_dis){
	if(now_dis > min_dis) return;
	if(now_cnt == n) min_dis = min(min_dis, now_dis);
	else{
		for(int i = 0; i < n; i++){
			if(idx[i] != -1) continue;

			idx[i] = now_cnt;
			int add_dis = 0;
			for(int j = 0; j < f_cnt[i]; j++){
				if(idx[friends[i][j]] != -1) add_dis += now_cnt - idx[friends[i][j]];
			}
			dfs(idx, now_cnt + 1, now_dis + add_dis);
			idx[i] = -1;
		}
	}
}

int main(){
	scanf("%d %d", &n, &m);
	for(int i = 0; i < m; i++){
		int a, b; scanf("%d %d", &a, &b);
		friends[a][f_cnt[a]++] = b;
		friends[b][f_cnt[b]++] = a;
	}

	int idx[11] = {0};
	for(int i = 0; i < n; i++) idx[i] = -1;
	dfs(idx, 0, 0);
	printf("%d\n", min_dis);

}