2496.txt

来自「北大ACM题目例程 详细的解答过程 程序实现 算法分析」· 文本 代码 · 共 57 行

Memory:104K  Time:62MS
Language:C++  Result:Accepted

Source 

#include <stdio.h>
#include <algorithm>

int e[100][100];
int n;
int p;
int a[10000];

int main()
{
	int cas, i, j, l, k, ans;
	
	scanf( "%d", &cas );
	
	for( l=1; l<=cas; l++ )
	{
		scanf( "%d", &p );
		scanf( "%d", &n );
		
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			scanf( "%d", &e[i][j] );


		for(k=0;k<n;k++)
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
			if(e[i][k]>=0 && e[k][j]>=0 
				&& ( e[i][k] + e[k][j] < e[i][j] || e[i][j] < 0 ) )
				e[i][j] = e[i][k] + e[k][j];

		k = 0;
		for(i=0;i<n;i++)
		for(j=0;j<n;j++)
		if( i != j  )
			a[k++] = e[i][j];

		std::sort( a, a+k );
		
		if( ( k*p ) % 100 == 0 )ans = ( k*p ) / 100-1;
		else ans = ( k*p ) / 100 ;
		
		printf( "Scenario #%d:\n", l );
		printf( "%d\n\n", a[ans] );
	}

	return 0;
}