#include<iostream.h>
#include<fstream.h> 
#include "park.h"

template<class T>
void Sample<T>::getdata ()             
	{
	ifstream infile ("park.dat");
	if(!infile)
	{
		cerr<< "error open"<< endl;
	}
		int i,j;

		cout<<"已從文件輸入公園景點的鄰接矩陣："<<endl;
		for(i=1;i<=6;i++)
		{	
			for(j=1;j<=6;j++)
			 {
				 infile>>park[i][j];
			 }
		}
		cout<<"輸入的公園景點的鄰接矩陣為："<<endl;
           for(i=1;i<=6;i++)
		{
			for(j=1;j<=6;j++) 
                cout<<park[i][j]<<"  ";
			cout<<endl;
	}

	cout<<endl;
}


template<class T>
void Sample<T>::ShortPath()      
		{
			int i,j,k;
            for (i=1;i<=6; i++) 
                for (j=1;j<=6; j++) 
				{ 
                   if (i==j) cost[i][j]=0;     //頂點本身假設無路徑 
				   else 
                        cost[i][j]=park[i][j]; 
				   path[i][j]=i;               
				}
            for (k=1; k<=6; k++) 
			{
                for (i=1; i<=6; i++)
				{
                    for (j=1; j<=6; j++) 
					{
                         if (cost[i][k]+cost[k][j]<cost[i][j]) 
						 { 
                             cost[i][j]=cost[i][k]+cost[k][j];  //加入k點
							 if (path[k][j]==k) 
							     path[i][j]=k;
							 else 
								 path[i][j]=path[k][j];         
						 }
		
					}
				}
			}

		cout<<"最小成本路徑長度 鄰接矩陣："<<endl;;
		for (i=1;i<=6;i++)
		{
			for (j=1;j<=6;j++)
			cout<<cost[i][j]<<" "; 
			cout<<endl;
        }
		cout<<endl;
		cout<<"相應路徑 鄰接矩陣："<<endl;
        for (i=1;i<=6;i++)
		{
			for (j=1;j<=6;j++)
			cout<<path[i][j]<<" ";
			cout<<endl;
		}
	cout<<endl;
}
template<class T>
void Sample<T>::display()              
{	
		int s,t;
		cout<<"請輸入兩個景點（1-A,2-B,3-C,4-D,5-E,6-F）：";
		cin>>s>>t;                    
          cout<<"景點間最短路徑長度："<<cost[s][t]<<endl;
          cout<<"走法為：";
	while (s!=t)
	{
		cout<<t<<" <-- ";                
		t=path[s][t];
	}
    cout<<s<<endl;
}



void main()                            
{	
	cout << "------------------------------最短路徑問題--------------------------------"<<endl;
	Sample<int> a;                     
	a.getdata();                       
    a.ShortPath();                  
    a.display();                       
}