comehome.cpp

USACO chapter two.Useful for beginners.

/*
ID: chenkai4
PROG: comehome
LANG: C++
*/
#include <iostream>
using namespace std;

#define MAXARRAY2 151

//--------封装2维数组---------
class _2int
{
public:
	double (*num)[MAXARRAY2];
	int u1,u2;
	_2int(int u1,int u2,int begin)
	{
		num = new double[u1][MAXARRAY2];
		memset(num,begin,sizeof(num));
	}
};
//----------------------------

//---------矩阵---------------
class _Matrix
{
public:
	double (*num)[MAXARRAY2];
	int Width,Height;
	_Matrix(const int width,const int height)
	{
		num = new double[width][MAXARRAY2];
		Width = width;Height = height;
		for(int a=0;a<width;a++)
			for(int b=0;b<height;b++)
				num[a][b]=0;
	}
};
//----------------------------

//----------加权图------------
class _WeightG
{
public:
	_Matrix *num;
	int Width,Height;
	_WeightG(const int vertexNum)
	{
		num = new _Matrix(vertexNum,vertexNum);
		Width = vertexNum;
		Height = vertexNum;
	}
};
//----------------------------

//------------Floyd------------
//Use:图中任意两点间最短距离
//O(n^3)
void Root(int p,int q,int *k,_2int *Path,int *Line)
{
	if (Path->num[p][q]>0)
	{
		Root(p,Path->num[p][q],k,Path,Line);
		Root(Path->num[p][q],q,k,Path,Line);
	}
	else 
	{
		Line[(*k)]=q;
		(*k)++;
	}
}

_2int* Floyd(_WeightG *thisG)
{
	int p,q,k,m;
	int Vertex = thisG->Height;int *Line;
	_2int *answer;
	answer = new _2int(Vertex,Vertex,0);
	for(p=0;p<Vertex;p++)
		for(q=0;q<Vertex;q++)
			answer->num[p][q]=thisG->num->num[p][q];
	for(k=0;k<Vertex;k++)
		for(p=0;p<Vertex;p++)
			if (answer->num[p][k]>0)
				for(q=0;q<Vertex;q++)
					if (answer->num[k][q]>0)
						if (((answer->num[p][q]>answer->num[p][k]+answer->num[k][q])||(answer->num[p][q]==0))&&(p!=q))
							answer->num[p][q]=answer->num[p][k]+answer->num[k][q];
	return answer;
}


//---------End Floyd----------
int N=0;

#define MAX(A,B) (A>B?A:B)
#define MIN(A,B) (A<B?A:B)
_2int *answer;
bool hash[200];
int nums[200];
char name[50];
int main()
{
	freopen("comehome.in","r",stdin);
	freopen("comehome.out","w",stdout);
	int p,t;char ch1,ch2;
	scanf("%d",&p);
	_WeightG thisG(60);
	for(int a=1;a<=p;a++)
	{
		scanf("\n%c %c %d",&ch1,&ch2,&t);
		if(!hash[(int)ch1])
		{nums[(int)ch1]=++N;
		name[N]=ch1;hash[(int)ch1]=true;}
		if(!hash[(int)ch2])
		{nums[(int)ch2]=++N;
		name[N]=ch2;hash[(int)ch2]=true;}
		if(nums[(int)ch1]!=nums[(int)ch2])
		{
			thisG.num->num[nums[(int)ch1]-1][nums[(int)ch2]-1]=(thisG.num->num[nums[(int)ch1]-1][nums[(int)ch2]-1]==0)?t:MIN(thisG.num->num[nums[(int)ch1]-1][nums[(int)ch2]-1],t);
			thisG.num->num[nums[(int)ch2]-1][nums[(int)ch1]-1]=thisG.num->num[nums[(int)ch1]-1][nums[(int)ch2]-1];
		}
	}
	thisG.Width = thisG.Height = N;
	answer = Floyd(&thisG);
	int minv=99999;char minc;
	for(int a=1;a<=N;a++)
	{
		if(name[a]<'Z'&&name[a]>='A')
			if(answer->num[nums[int('Z')]-1][nums[(int)name[a]]-1]<minv)
			{
				minc=name[a];
				minv=answer->num[nums[int('Z')]-1][nums[(int)name[a]]-1];
			}
	}
	printf("%c %d\n",minc,minv);
	return 0;
}