Poj Solution 2496

http://poj.org/problem?id=2496

#include <stdio.h>
#include <algorithm>
using namespace std;

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( "%dnn", a[ans] );
    }

    return 0;
}
											
This entry was posted in poj. Bookmark the permalink.

Leave a Reply

Your email address will not be published. Required fields are marked *