> #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;
> 
> }

• 此贴作废！当初太弱了！现在ac了！ (0) ericsummer 2006-01-04 12:19:10