//動(dòng)態(tài)規(guī)劃法之公園導(dǎo)游問(wèn)題
//程序源代碼
#include<iostream.h>
#define MAX 100
int n;                                         //公園景點(diǎn)個(gè)數(shù) 
template<class T>                              //定義模板 
class Sample                                   //定義Sample為類模板
{
	T park[MAX][MAX],cost[MAX][MAX],path[MAX][MAX]; 
	//park[n][n]是記錄公園景點(diǎn)圖的成本鄰接矩陣；cost[i][j]是記錄vi到vj的最小成本路徑的長(zhǎng)度；
    //path[i][j]是記錄最小成本的路徑。
	public:
	    Sample(){n=0;}
		void getdata ();                       //數(shù)據(jù)輸入函數(shù)
		void shortestpaths();                  //求最短路徑函數(shù)
		void display();                        //結(jié)果輸出函數(shù) 
};
		template<class T>
		void Sample<T>::getdata ()             //數(shù)據(jù)輸入
		{
			int i,j;
			cout<<"公園景點(diǎn)的個(gè)數(shù)為：";
			cin>>n;
			cout<<"請(qǐng)輸入公園景點(diǎn)的鄰接矩陣："<<endl;
			for(i=1;i<=n;i++)
			{	cout<<"請(qǐng)輸入公園景點(diǎn)"<<i<<"到其它景點(diǎn)的距離：";
                 for(j=1;j<=n;j++)
				 {
					 cin>>park[i][j];
				 }
				 cout<<endl;
			}
			cout<<"輸入的公園景點(diǎn)的鄰接矩陣為："<<endl;
            for(i=1;i<=n;i++)
			{
				for(j=1;j<=n;j++)
	                 cout<<park[i][j]<<" ";
                cout<<endl;
			}
			cout<<endl;
		}
		template<class T>
		void Sample<T>::shortestpaths()        //求最短路徑
		{
			int i,j,k;
            for (i=1;i<=n; i++) 
                for (j=1;j<=n; j++) 
				{ 
                   if (i==j) cost[i][j]=0;     //頂點(diǎn)本身假設(shè)無(wú)路徑 
				   else 
                        cost[i][j]=park[i][j]; //復(fù)制
				   path[i][j]=i;               //初始化路徑
				}
            for (k=1; k<=n; k++) 
			{
                for (i=1; i<=n; i++)
				{
                    for (j=1; j<=n; j++) 
					{
                         if (cost[i][k]+cost[k][j]<cost[i][j]) 
						 { 
                             cost[i][j]=cost[i][k]+cost[k][j];  //加入k點(diǎn)
							 if (path[k][j]==k) 
							     path[i][j]=k;
							 else 
								 path[i][j]=path[k][j];         //加入k點(diǎn)后修改路徑
						 }
					}
				}
			}
			cout<<"最小成本路徑長(zhǎng)度的鄰接矩陣為："<<endl;;
			for (i=1;i<=n;i++)
			{
				for (j=1;j<=n;j++)
					cout<<cost[i][j]<<" "; 
				cout<<endl;
            }
			cout<<endl;
			cout<<"相應(yīng)的路徑鄰接矩陣為："<<endl;
            for (i=1;i<=n;i++)
			{
				for (j=1;j<=n;j++)
					cout<<path[i][j]<<" ";
				cout<<endl;
			}
			cout<<endl;
		}
		template<class T>
		void Sample<T>::display()              //結(jié)果輸出
		{	
			char time;                         //time控制輸入選擇景點(diǎn)的次數(shù)
			time='Y';
			while (time=='Y')               
			{
			int s,t;
			cout<<"請(qǐng)輸入兩個(gè)景點(diǎn)：";
				cin>>s>>t;                     //任意輸入兩個(gè)景點(diǎn)
            cout<<"兩個(gè)景點(diǎn)之間的最短路徑長(zhǎng)度為："<<cost[s][t]<<endl;
            cout<<"相應(yīng)的走法為：";
			while (s!=t)
			{
				cout<<t<<"<-";                 //采用從后向前標(biāo)記路徑
				t=path[s][t];
			}
		  cout<<s<<endl;
		  cout<<"是否繼續(xù)？（如果繼續(xù)，請(qǐng)輸入Y，否則請(qǐng)輸入NO）：";
		     cin>>time;                        //鍵入Y，可以多次選擇景點(diǎn) 
			}
		}
        void main()                            //主函數(shù)
		{
			Sample<int> a;                     //聲明一個(gè)模板類的對(duì)象a
			a.getdata();                       //通過(guò)訪問(wèn)對(duì)象的公有成員函數(shù)，實(shí)現(xiàn)數(shù)據(jù)輸入
	        a.shortestpaths();                 //求解最短路徑
	        a.display();                       //輸出結(jié)果，即最短路徑值和相應(yīng)的走法
		
		}