#include <list>
#include <iostream>

using namespace std ;

typedef list<int> LISTINT;

LISTINT listAnother;
LISTINT list_result;

int d[5][5]={{-1,20,30,10,11},{15,-1,16,4,2},{3,5,-1,2,4},{19,6,18,-1,3},{16,4,7,16,-1}};
int    matrix_length=5;

int getPath(int n,LISTINT list_org)
{     
	   
	//	cout<<"-------------------"<<n<<"-start-------"<<endl;
     	LISTINT::iterator i;
	   
	   int minValue;
       if(n==1){
       i=list_org.begin();
       minValue= d[*i-1][0];
	   if(list_org.size()==matrix_length-1){
          list_result=list_org;
	   }
	   //cout<<"---"<<*i<<"-"<<"1"<<"="<<minValue<<endl;
      
	   }
	   else{
	   int temp;
	   i=list_org.begin();
	   temp=*i;
       list_org.erase(i);
	   i=list_org.begin();
       minValue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
        if(list_org.size()==matrix_length-1){
          list_result=list_org;
	   }
		/*
	   cout<<"----"<<temp<<"--"<<*(i)<<"="<<minValue<<"--鏈表里還剩有如下元素";
	    for (i = list_org.begin(); i != list_org.end(); ++i)
        cout << *i << " ";
        cout << endl;
	    */
       for(int j=2;j<n;j++)
	   {  
		    i=list_org.begin();
		   for(int k=1;k<j;k++){               
               i++;
		   }
           
          int tempvalue=*i;
		  list_org.erase(i);
		  list_org.push_front(tempvalue);
		  i=list_org.begin();
          tempvalue=d[temp-1][*(i)-1]+getPath(n-1,list_org);
	    /*
		   cout<<"----"<<"---"<<temp<<"--"<<*(i)<<"="<<tempvalue<<"--所有的";
	    for (i = list_org.begin(); i != list_org.end(); ++i)
        cout << *i << " ";
        cout << endl;
		*/
		  if(tempvalue<minValue){
			   if(list_org.size()==matrix_length-1){
                  list_result=list_org;
			   }
              minValue=tempvalue;
		  }

	   }
	   }


	//cout<<"-------------------"<<n<<"---end-----"<<endl;
return minValue;
}
int main(int argc, char* argv[])
{

LISTINT list_org;
LISTINT::iterator h;
list_org.push_front(5);
list_org.push_front(4);
list_org.push_front(3);
list_org.push_front(2);
list_org.push_front(1);
cout<<"旅行商問(wèn)題的動(dòng)態(tài)規(guī)劃算法"<<endl;
cout<<"路線長(zhǎng)度的矩陣表示如下,-1表示無(wú)限大"<<endl;
for(int j=0;j<matrix_length;j++){
	cout<<endl;
	for(int k=0;k<matrix_length;k++){
		cout<<" "<<d[j][k];
	}
}
cout<<endl;
		

cout<<"計(jì)算結(jié)果:"<<getPath(5,list_org)<<endl;
list_result.push_front(1);
list_result.push_back(1);
cout<<"走的路徑:---->:";
for (h = list_result.begin(); h != list_result.end(); ++h)

     cout << *h << " ";

        
        cout << endl;
int i;
cin>>i;
return 0;
}