好最短路径正常501biminp.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
int last(int aa[],int nn,int bb[],int mm)////////////函数有问题
{
	int ct;
	while(aa[nn-1]==bb[mm-1])
	{
		nn--;
		mm--;
	}//当数组aa和bb遇到不相同元素时退出循环
	ct=nn+mm;
	return ct;//ct就是两个结点的最短路径长度
}



int n,m,i,j,pq,t1,t2,p,length1,length2,temp1[80000],temp2[80000];
int main()
{
	ifstream in("input.txt");
	if(in.fail())
	{
		cout<<"the input.txt is not exist!";
		exit(1);
	}
	ofstream out("output.txt");
	in>>n;//输入结点个数
	int *get=new int[n+1];//父结点数组表示法///n+1
	int *a=new int[n];/////n
	int *b=new int[n];/////n
	int *c=new int[n];/////n
	get[1]=0;
	for(i=0;i<n;i++)
	{
		in>>a[i]>>b[i]>>c[i];//输入数据,并建立
		get[b[i]]=a[i];
		get[c[i]]=a[i];
	}
	pq=a[0];///根结点
	in>>m;
	int *d=new int[m];////m
	int *e=new int[m];/////m
	int *r=new int[m];//用来存放最短路径的长度////m
	for(i=0;i<m;i++)
	{
		in>>d[i]>>e[i];//要计算最短路径的结点编号
		temp1[0]=d[i];//每个数组的第一个元素总是结点编号
		temp2[0]=e[i];//每个数组的第一个元素总是结点编号
		t1=d[i];
		t2=e[i];
		for(j=1;t1!=pq;j++)//注意：j从1开始，且有等号
		{
			temp1[j]=get[t1];//建立相连的结点数组
			t1=get[t1];
		}//注意循环结束的条件!!
		if(j!=1)
			length1=j;//指示数组temp1的元素个数
		else
			length1=1;
	/*	for(kk=0;kk<j;kk++)
			out<<temp1[kk]<<' ';
		out<<endl;*/
		for(j=1;t2!=pq;j++)//注意：j从1开始，且有等号
		{			
			temp2[j]=get[t2];//建立相连的结点数组		
			t2=get[t2];
		
		}//注意循环结束的条件!!
		if(j!=1)
			length2=j;//指示数组temp1的元素个数
		else
			length2=1;
		if(d[i]==e[i])/////要注意考虑多中情况
			r[i]=0;
		else 
			if(d[i]==pq||e[i]==pq)
			r[i]=length1+length2-2;
		else
			r[i]=last(temp1,length1,temp2,length2);	
	}
		
	//////////////////////////////////////
	for(i=0;i<m;i++)
		out<<d[i]<<' '<<e[i]<<' '<<r[i]<<endl;
	delete []get;
	delete []a;
	delete []b;
	delete []c;
	delete []d;
	delete []e;  
	delete []r;
	return 1;
}