//*************************************************************
//*程序AlgBB用于求解甲乙城市之間的最短路徑的分支限界問題	  *
//*輸入：距離文件m1.txt，耗費文件m2.txt						  *
//*輸出：甲乙城市間的具體最短路徑及其總長度和總耗費		      *
//*************************************************************

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

const int MAX=9999;

//類HeapNode：用于構造類的節點
class HeapNode
{
	public:
		HeapNode()
		{
			n=0;
		}
		HeapNode(const HeapNode& );
		HeapNode& operator=(const HeapNode&);
		int length;		//當前路徑長度的邊界
		int cost;		//所耗養路費的值
		int num;		//城市的編號
		int path[50];	//到該節點所經過的路徑
		int n;			//路徑中的頂點數（城市數）
};

//構造函數
HeapNode::HeapNode(const HeapNode& a)
{
	int i;
	length=a.length;
	cost=a.cost;
	num=a.num;
	n=a.n;
	for(i=0;i<a.n;i++)
	{
		path[i]=a.path[i];
	}
}

//賦值操作符重載
HeapNode& HeapNode::operator =(const HeapNode& a)
{
	int i;
	length=a.length;
	cost=a.cost;
	num=a.num;
	n=a.n;
	for(i=0;i<a.n;i++)
	{
		path[i]=a.path[i];
	}
	return *this;
}

//類Heap：用于最小堆的構造
class Heap
{
	public:
		Heap(int heapSize);				//構造函數
		void delNode(HeapNode & x);		//從堆中刪除最小元素
		void insNode(HeapNode & x);		//向堆中插入元素
		bool isEmpty();					//判斷堆是否為空
	private:
		int size;						//堆的最大容量
		int n;							//當前堆的大小
		HeapNode * heap;				//指向堆的指針
		void moveUp(int i);				//用于在堆中從下到上交換元素
		void moveDown(int i);			//用于在堆中從上到下交換元素
};

//構造函數
Heap::Heap(int heapSize)
{
	heap=new HeapNode[heapSize];
	size=heapSize;
	n=0;
}

//判斷堆是否為空
bool Heap::isEmpty()
{
	if(n<=0)
	{
		return true;
	}
	else
	{
		return false;
	}
}

//用于在堆中從下到上交換元素
void Heap::moveUp(int i)
{
	while(i>0)
	{
		if(heap[i].length < heap[(i-1)/2].length)
		{
			HeapNode a=heap[i];
			heap[i]=heap[(i-1)/2];
			heap[(i-1)/2]=a;
			i=(i-1)/2;
		}
		else 
		{
			return;
		}
	}
	return;
}

//用于在堆中從上到下交換元素
void Heap::moveDown(int i)
{
	while((2*i+1) < n)
	{
		i=2*i+1;
		if(i+1<n)
		{
			if(heap[i].length > heap[i+1].length)
			{
				i=i+1;
			}
		}
		if(heap[(i-1)/2].length > heap[i].length)
		{
			HeapNode a=heap[i];
			heap[i]=heap[(i-1)/2];
			heap[(i-1)/2]=a;
		}
		else
		{
			return;
		}
	}
	return;
}

//從堆中刪除最小元素
void Heap::delNode(HeapNode& x)
{
	x=heap[0];
	heap[0]=heap[n-1];
	if(--n<=0)
	{
		return;
	}
	moveDown(0);
}

//向堆中插入元素
void Heap::insNode(HeapNode& x)
{
	heap[n++]=x;
	moveUp(n-1);
	
}

//利用分枝定界法求解最短路徑
void AlgBB(int cost[51][51],int length[51][51])
{
	int i,j,tmp,u,n,min,shortestCost,s[51];
	int distance[51];			//用于存放到目的地最短路徑長度
	int path[50];				//到目前為止的最短路徑
	int pathLength=0;			//目前路徑中包含的結點數

	Heap heap(200);				//構造堆
	HeapNode node;
	n=50;
	min=MAX;
	node.num=1;
	node.cost=0;
	node.path[node.n++]=1;

	for(i=1;i<n;i++)
	{
		distance[i]=length[i][50];
		s[i]=false;
	}
	for(i=1;i<n;i++)
	{
		tmp=MAX;
		for(j=1;j<n;j++)
		{
			if(!s[j] && (distance[j]<tmp))
			{
				tmp=distance[j];
				u=j;
			}
		}
		if(tmp<MAX)
		{
			s[u]=true;
			for(j=1;j<n;j++)
			{
				if(!s[j] && (distance[u]+length[j][u]<distance[j]))
				{
					distance[j]=distance[u]+length[j][u];
				}
			}
		}
	}

	node.length=distance[1];

	//遍歷解空間樹
	for(;;)
	{
		for(i=1;i<=n;i++)
		{
			//判斷是否剪枝
			if((length[node.num][i] < MAX) && (node.cost+cost[node.num][i]<=1500) && (node.length-distance[node.num]+length[node.num][i]+distance[i]<=min))
			{
				//是否到達目的地
				if(i==50)
				{
					if(node.length+length[node.num][i]-distance[node.num]<=min)
					{
						for(j=0;j<node.n;j++)
						{
							path[j]=node.path[j];
						}
						path[node.n]=50;
						pathLength=node.n+1;
						min=node.length+length[node.num][i]-distance[node.num];
					}				
					continue;
				}

				//查看是否出現回路
				for(j=0;j<node.n;j++)
				{
					if(node.path[j]==i)
					{
						break;
				
					}
				}
				//將節點其插入最小堆中
				if(node.n==j)
				{
					HeapNode tmp;
					tmp.num=i;
					tmp.length=node.length-distance[node.num]+length[node.num][i]+distance[i];
					tmp.cost=node.cost+cost[node.num][i];
					tmp.n=node.n+1;
					for(j=0;j<node.n;j++)
					{
						tmp.path[j]=node.path[j];
					}
					tmp.path[node.n]=i;
					heap.insNode(tmp);
				}
			}
		}

		//每次從優先隊列中取一個最小的結點
		while(true)
		{
			//如果隊列為空則輸出結果
			if(heap.isEmpty())
			{
				cout<<"算法AlgBB所得結果:"<<endl;
				cout<<"甲乙之間最短路線長度是:"<<min<<endl;
				shortestCost=0;
				for(i=0;i<pathLength-1;i++)
				{
					shortestCost+=cost[path[i]][path[i+1]];
				}
				cout<<"最短路線收取的費用是:"<<shortestCost<<endl;
				cout<<"最短路徑是:"<<endl;
				for(i=0;i<pathLength;i++)
				{
					cout<<path[i]<<"	";
				}
				cout<<endl;
				return;
			}
			//隊列不為空則取出堆中的最小結點
			heap.delNode(node);
			//判斷是否剪枝
			if(node.length>min)
			{
				continue;
			}
			else
			{
				break;
			}
		}
	}
}

int main()
{
	int i,j,n;
	int cost[51][51];						//耗費矩陣
	int length[51][51];						//距離矩陣

	ifstream inFile;			
	//讀文件m1.txt到length矩陣中
	inFile.open("m1.txt");					
	n=50;
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			inFile>>length[i][j];
		}
	}
	inFile.close();
	//讀文件m2.txt到cost矩陣中
	inFile.open("m2.txt");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
		{
			inFile>>cost[i][j];
		}
	}
	inFile.close();
	//調用分支限界函數求解
	AlgBB(cost,length);
	return 1;
}