TSPcut.c

#include <omp.h>
#include <stdlib.h>
#include <stdio.h>

#define MAX_N 100
#define X 0
#define Y 1

int N;
int map[MAX_N][2];
int min_distance = 2147483647;

void queen(int position[], int next, int current_distance, int went[])
{


	int test;

	if (next >= N) {
		if(current_distance < min_distance){
			min_distance = current_distance;
		}
		return;
	}

	for (test = 0; test < N; test++) {
	//	if (ok(position, next, test)) {
		if (!went[test]) {
			position[next] = test;

			int dx = map[position[next]][X] - map[position[next-1]][X];
			int dy = map[position[next]][Y] - map[position[next-1]][Y];
			double test_distance = current_distance + dx * dx + dy * dy;
			if(test_distance > min_distance)
				continue;


			went[test] = 1;
			queen(position, next + 1, test_distance, went);
			went[test] = 0;
		}
	}
}


int main(int argc, char *argv[])
{
	scanf("%d", &N);
	int i;

	for(i = 0; i < N; i++){
		scanf("%d %d", &map[i][X], &map[i][Y]);
	}


	int position[MAX_N] = {0};
	int went[MAX_N] = {0};
	for(i = 0; i < N; i++){
		position[0] = i;
		went[i] = 1;
		queen(position, 1, 0, went);
		went[i] = 0;
	}
	printf("%d\n", min_distance);

	return 0;
}