assemble line.cpp

经典算法实现

#include "Assemble Line.h"
#define MAX -1;

int stationNum;
int *stationCostL,*stationCostR;
int *jumpL2R,*jumpR2L;
int *fastestL,*fastestR;//记录目前的最短路径
int inL,inR,outL,outR;
bool *preL,*preR,*path;//最短路径从preL[i]到i号L－station,path标识最短路径
bool final;

int Fastest(bool lorr,int num){
	//unsigned min = (unsigned)(-1);
	
	if (lorr==0){//0=left
		
		if(fastestL[num]>0){
			return fastestL[num];
		
		}
		else if(num ==0){
			 fastestL[0]=inL+stationCostL[0];
			 return fastestL[0];
			 
		}
		

		else{
			
			int L=Fastest(0,num-1)+stationCostL[num];
			int R=Fastest(1,num-1)+stationCostL[num]+jumpR2L[num-1];
			
			if(L<R){	
				preL[num]=0;
				return fastestL[num] = L;
			//	return L;
			}

			if(R<L){
				preL[num]=1;
				return fastestL[num] = R;
				//return R;
			}
			//return L<R?L:R;
			//return min;
		}
	}
	
	else{//1=right
		if(fastestR[num]>0){
			return fastestR[num];
		
		}

		else if(num ==0)
			return fastestR[num] = inR+stationCostR[0];

		else{
			int L=Fastest(0,num-1)+jumpL2R[num-1]+stationCostR[num];
			int R=Fastest(1,num-1)+stationCostR[num];

			if(L<R){	
				preR[num]=0;
				return fastestR[num]= L;
			}

			if(R<L){
				preR[num]=1;
				return fastestR[num] =R;
				//return R;
			}
		}
	}
	//cout<<max;

}

int main(){

	/*int stationNum;
	int *stationCostL,*stationCostR;
	int *jumpL2R,*jumpR2L;
	int inL,inR,outL,outR;*/

	ifstream arg("F:\\twh\\Algorithm Itr\\Assemble Line\\input.txt");
	ofstream result("F:\\twh\\Algorithm Itr\\Assemble Line\\output.txt");
	
	if ( !arg ) { // opened failed
     cerr << "cannot open F:\\twh\\Algorithm Itr\\Assemble Line\\input.txt for input"<<endl;
     exit( -1 );
	}

	if ( !result ) { // opened failed
     cerr << "cannot open F:\\twh\\Algorithm Itr\\Assemble Line\\output.txt for output"<<endl;
     exit( -1 );
	}

	arg>>stationNum;

	stationCostL = new int[stationNum];
	stationCostR = new int[stationNum];
	jumpL2R = new int[stationNum-1];
	jumpR2L = new int[stationNum-1];
	
	fastestL = new int[stationNum];
	fastestR = new int [stationNum];
	
	preL = new bool [stationNum];
	preR = new bool [stationNum];

	path = new bool [stationNum];

	for (int i=0;i<stationNum;i++){
		fastestL[i]=0;
		fastestR[i]=0;
	}

	for(int i=0;i<stationNum;i++)
		arg>>stationCostL[i];

	for(int i=0;i<stationNum;i++)
		arg>>stationCostR[i];

	for(int i=0;i<stationNum-1;i++)
		arg>>jumpL2R[i];
	for(int i=0;i<stationNum-1;i++)
		arg>>jumpR2L[i];

	arg>>inL>>outL>>inR>>outR;

	arg.close();

	int L = Fastest(0,stationNum-1)+outL;
	int R = Fastest(1,stationNum-1)+outR;
	
	int min =L<R?L:R;

	//cout <<"final is"<<final; 
	for(int i=0;i<stationNum;i++){
		result << fastestL[i]<<" ";
	}
	
	result<<endl;

	for(int i=0;i<stationNum;i++){
		result << fastestR[i]<<" ";
	}
	
	result<<endl;
	
	/*for(int i=1;i<stationNum;i++){
		cout << preR[i]<<" ";
	
	}

	cout <<endl;*/

	if(L<R)	final =0;
	else final =1;

	path[stationNum-1]=final;
	bool pre=final;
	for(int i=stationNum-1; i>0; i--){

		if(pre){	
			path[i-1] = preR[i];
			pre = preR[i];
		}
		else {
			path[i-1] =preL[i];
			pre = preL[i];	
		}
	}

	for(int i=0;i<stationNum;i++)
	{
		result <<path[i]<<" ";
	}

	result <<endl;

	result <<L <<" "<<R<<endl;

	result <<"The fastest way costs "<<min<<" minutes."<<endl; 
	

	
	//cout <<Fastest(1,1);//<<" "<<Fastest(1,1)<<endl;

//	int min=L<R?L:R;
	
	//cout<< min <<endl;

	//Fastest(1,1);
	//test input;
	/*cout<<stationNum<<endl;

	for(int i=0;i<stationNum;i++){
		cout<<stationCostL[i]<<" ";
	}
	
	cout<<endl;

	for(int i=0;i<stationNum;i++){
		cout<<stationCostR[i]<<" ";
	}

	cout<<endl;

	for(int i=0;i<stationNum-1;i++)
		cout<<jumpL2R[i]<<" ";
	
	cout<<endl;

	for(int i=0;i<stationNum-1;i++)
		cout<<jumpR2L[i]<<" ";

	cout<<endl;
	
	cout<<inL<<" "<<outL<<endl<<inR<<" "<<outR<<endl;*/


}