//鄰近法求解TSP問題的主程序

#include <iostream>
#include <fstream>
#include <string>
#include <cmath>
using namespace std;

int main()
{
	//申明和初始化變量
	int path[20];
	float sum_length;
	float city_distance[20][20];
	float max_distance, min_distance;
	int i=0, k=0, j=0,t=0;
	int min_path;
	string filename="distance.txt";
	ifstream sensor;

	//打開文件讀取距離數據信息
	sensor.open(filename.c_str());
	if(sensor.fail())
	{
		cout<<"Error opening input file\n";
	}
	else
	{
		//沒有到達文件末尾時循環讀取數據

		sensor>>max_distance>>min_distance;
		//cout<<max_distance<<min_distance;
	
		
		while(!sensor.eof())
		{
			for(i=0;i<20;i++)
			{
				for(j=0;j<20;j++)
				{
					sensor>>city_distance[i][j];
				}
				city_distance[i][i]=max_distance+1;
			}
		}
	}


	//求解最短路徑
	
	k=0;
	i=0;
	t=0;
	sum_length=0;
	
	while(k<20)
	{
	    path[k]=i;
		min_path=city_distance[i][0];
		for(j=0;j<20;j++)
		{
			if(min_path>city_distance[i][j])
			{
				min_path=city_distance[i][j];
				t=j;
			}
		}
		sum_length+=city_distance[i][t];
		i=t;
		for(j=0;j<=k;j++)
		{
			city_distance[i][path[j]]=max_distance+1;
		}

		k++;
	}

	cout<<"the result of the path:"<<endl;

	for(j=0;j<20;j++)
	{
		cout<<char(path[j]+65)<<' ';
	}

	cout<<endl<<"the total length is: "<<sum_length<<endl;


	return 0;
}