/*最近傍法　（Nearest Neighbor Algorithm）
始点都市をA_1とした巡回路の構築
実行： ./tspnn A_1

都市iのx座標とy座標をそれぞれx[i],y[i]とする
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define n 281        //都市の数
int keiro[n+1];   //都市の辿る順番を格納する配列
int x[n+1],y[n+1];//座標
int **d;

//都市iと都市jの距離を求める
int eud2d(int i, int j ,int x[],int y[])
{
	double xd,yd;
	

	xd=x[i]-x[j];
	yd=y[i]-y[j];

	return (int) (sqrt(xd*xd+yd*yd)+0.5);
	
		
}

int nearest(int i,int **d,int count){ 
	int j;
	int near_d;//都市iとの最短距離
	int near_j;//都市iから最も近い都市j

			  
	if(count==n-1){   //最後まで行ったら都市1に戻る
		keiro[i]=keiro[0];
		printf("%d %d %d %d %d %d\n",count,i,keiro[i],d[i][keiro[0]],x[i],y[i]);
		printf("%d %d 0 0 %d %d\n",count+1,keiro[i],x[keiro[i]],y[keiro[i]]);
		return d[i][1];
	}else{
		
			//都市iから最も近い都市を求める
		near_d=99999;
		for(j=1;j<n;j++){
			if(keiro[j]==0 && i!=j && near_d>d[i][j] ){
				near_d=d[i][j];      
				near_j=j;   
			//	printf("%d %d %d \n",i,near_j,near_d);
				
			}
			
		}
		keiro[i]=near_j ; //iの次の都市番号をkeiro[i]に格納
		
		printf("%d %d %d %d %d %d\n",count,i,keiro[i],near_d,x[i],y[i]);
		//count 現在の都市　次の都市　 距離　現在の都市の座標
		count ++;
		return near_d + nearest(near_j,d,count);
	}
		free(keiro);
}




//第1引数をA_1とする
int main(int argc,char **argv){
	FILE *fp;
	char fname[]="a280.tsp";
	int read_n,read_x,read_y ; //読み込み用
	int i,j; //都市番号

//	int d;//距離			    
//	int keiro[n+1];   //都市の辿る順番を格納する配列
	int distance; //総移動距離
	int count; //都市の数を数える
	int A_1; //最初の都市

	if (argc == 2) {
		sscanf(argv[1], "%d", &A_1); //第1引数argv[1]をA_1に代入
		//	printf("A_1 = %d\n",A_1);
	}
	
	fp = fopen(fname, "r"); // ファイルを開く。失敗するとNULLを返す。
	if(fp == NULL) {
		printf("%s file not open!\n", fname);
		return -1;
	}
	/*else {
		printf("%s file opened!\n", fname);
	}
	*/
	// ファイルからデータを読み込み格納

	while(fscanf(fp, "%d %d %d ", &read_n, &read_x, &read_y) != EOF) {
		//	printf(" %d %d %d \n", read_n, read_x, read_y);
		x[read_n]=read_x;
		y[read_n]=read_y;
		//	printf(" %d %d %d \n", read_n,	x[read_n], y[read_n]);
		
	}
//メモリの確保
	d = (int**)malloc(sizeof(int*) * n);
        rep(i,n)
                d[i] = (int*)malloc(sizeof(int)*n);
	
	for(i=1;i<n;i++){
		for(j=1;j<n;j++){
			d[i][j]=eud2d(i, j ,x,y);	//計算した距離を格納
			// 	printf("%d %d %d\n",i,j,d[i][j]);
		}
	}



	for(i=0;i<n;i++){  
		keiro[i]=0;
    	}
	count=1;
	keiro[0]=A_1;  //最初の都市を設定
       	distance=nearest(keiro[0],d,count);
	
        //最短距離 
	printf("%d\n",distance);

	rep(i,n)
                free(d[i]);
        free(d);


	fclose(fp); // ファイルを閉じる
 
	
 
	return 0;

}