好最短路径二634minp.cpp

设计一个算法

#include<iostream>
#include<fstream>
using namespace std;
int n,i,j=1,k;
int main()
{
	ifstream in("input.txt");
    if(in.fail())
	{
		cout<<"the input.txt is not exit!";
		exit(1);
	}
	ofstream out("output.txt");
    in>>n;
	int *a=new int[n+1],*t=new int[n];
	a[1]=0;
	for(i=0;i<n;i++)
	{
		in>>t[i];
		if(t[i]==0)
		{
			j++;
			continue;
		}
	    int *b=new int[t[i]];
	    for(k=0;k<t[i];k++)
		{
			in>>b[k];
			a[b[k]]=j;
		}
		j++;
		delete[]b;
	}
	int l;
    in>>l;
	int *p=new int[2*l];
	for(i=0;i<2*l;i++)
		in>>p[i];
    int x,y;
	int length,length1,length2;
	for(i=0;i<2*l;i+=2)
	{
		int *c=new int[n];
		int *d=new int[n];
		length1=0;
		length2=0;
		x=p[i];
		y=p[i+1];
		c[length1]=x;
	    d[length2]=y;
		while(x!=1)
		{
			length1++;
			c[length1]=a[x];
			x=a[x];
		}
        while(y!=1)
		{
			length2++;
			d[length2]=a[y];
			y=a[y];
		}
		int u,v,w=0;
		for(int r=0;r<=length1;r++)
		{
			for(int s=0;s<=length2;s++)
				if(c[r]==d[s])
				{
					u=r;
					v=s;
					w=1;
				}
			if(w==1)
				break;
		}
		length=u+v;
        out<<p[i]<<" ";
		out<<p[i+1]<<" ";
		out<<length<<endl;
		delete[]c;
		delete[]d;
	}
	delete[]p;
	delete[]t;
	delete[]a;
	return 0;
}