如题，谢了
#include<iostream>
using namespace std;
int main()
{
	int n;
	while(cin>>n&&n!=0)
	{
		int i,j,a,u,v,k,t1,t2,t3,t=32767,q,t0;
		int *min=new int [n+1];
		for(i=0;i<n+1;i++)
			min[i]=0;
		int **c=new int *[n+1];
		for(i=0;i<n+1;i++)
			c[i]=new int [n+1];
		for(i=1;i<=n;i++)
			for(j=1;j<=n;j++)
				c[i][j]=32767;
		for(i=0;i<n;i++)
		{
			cin>>a;
			for(j=0;j<2*a;j=j+2)
			{
				cin>>u>>v;
				c[i+1][u]=v;
			}
		}
		for(i=1;i<=n;i++)
			c[i][i]=0;
		for(k=1;k<=n;k++)//Floyd算法
			for(i=1;i<=n;i++)
				for(j=1;j<=n;j++){
					t1=c[i][k];
					t2=c[k][j];
					t3=c[i][j];
					if(t1!=32767&&t2!=32767&&(t3==32767||t1+t2<t3)){
						c[i][j]=t1+t2;
					}
				}
		for(i=1;i<=n;i++)//寻找路径
		{
			for(j=1;j<=n;j++)
				min[i]=c[i][j]+min[i];
			if(min[i]<t)
			{
				t=min[i];
				q=i;
				t0=c[i][n-1];
			}
		}
        if(t==32767)
		   cout<<"disjoint"<<endl;
		else cout<<q<<" "<<t0<<endl;
	}
	return 0;
}

• Re:我用Floyd算法不知错哪了，大牛帮看下 (1129) phoenixzz 2007-07-20 20:25:40