#include <iostream.h>

inline void swap( int &a , int &b)
{
	int t;
	t=a ; a=b ;b=t;
}

int partition(int a[] , int p , int r)
{
	int x=a[r];

	int i=p-1 ;

	for( int j=p ; j < r ; j++)
	{
		if(a[j] <=x)
		{
			i++;
			swap( a[i] , a[j]);

		}
	}

	swap( a[i+1] , a[r]);

	return i+1 ;

}

void quicksort(int a[] , int p , int r)
{
	if( p <r )
	{
		int q= partition(a , p , r);
		quicksort(a , p , q-1);
		quicksort(a , q+1 ,r);
	}

	return ;
}


int main()
{
	int a[101][101];

	int c[10201];

	int N , p ,n , i , j ,k , l ,count=0;

	cin >> N ;

	while(N--)
	{
		count++;

		cin >> p >> n;

		for( i = 1 ; i <= n ; i++)
			for( j = 1 ; j<= n ; j++)
				cin >> a[i][j];

        for( i =1 ; i<=n ;i++)
		{
			for( j=1 ;j<=n ;j++)
			{
				if(a[i][j]==-1)
				{
					int m=0;

					int b[100];


					for( k= 1 ; k<= n ; k++)
					{
						if( k==i || k== j) continue ;

						if( a[i][k]!=-1 && a[k][j]!=-1)
							b[++m]=a[i][k]+a[k][j];
					}

					int min=b[1];

					for( l=2 ;l<=m ;l++)
						if(min > b[l]) min=b[l];

						a[i][j]=min;

					
				}
			}
		}
		int m=0;

		for( i = 1 ; i<= n ;i++)
		{
			for( j =1 ;j<=n ; j++)
				if( i!= j) c[++m]=a[i][j];
		}

		quicksort(c ,1 ,m);

		if(n*(n-1)*p%100)
		{
			cout << "Scenario #" << count << ":"<< endl;

			cout << c[n*(n-1)*p/100+1] << endl << endl;
		}

		else
		{
			cout << "Scenario #" << count << ":" <<endl;

			cout << c[n*(n-1)*p/100] << endl << endl;

		}





		
	}

	return 0;

}

• Re:who can help me ,what's wrong with my program? help ! (1839) ericsummer 2006-01-04 12:18:06
  • 此贴作废！当初太弱了！现在ac了！ (0) ericsummer 2006-01-04 12:19:10