2644091_ac_46ms_196k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <math.h>
#include <algorithm>
#define INF 100000000

using namespace std;

int map[101][101];
int n;
int dis[101*101];

void floyd()
{
	int i, j, k;
 
	for(k = 0; k < n; k++)
	{
		for(i = 0; i < n; i++)
		{
			if(map[i][k]!=INF)
			{
				for(j = 0; j < n; j++)
					if(map[i][k]+map[k][j]<map[i][j])
						map[i][j]=map[i][k]+map[k][j]; 
			}
		}  
	}
}

int main()
{
	int t, cas, p;
	int i, j;

	scanf("%d",&t);
	cas = 1;
	while (t--)
	{
		scanf("%d%d",&p,&n);
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				scanf("%d",&map[i][j]);
				if (map[i][j]<=0)
				{
					map[i][j] = INF;
				}
			}
		}
		floyd();
		int l = 0;
		for (i = 0; i < n; i++)
		{
			for (j = 0; j < n; j++)
			{
				if (i!=j)
				{
					dis[l++] = map[i][j];
				}
			}
		}
		sort(dis,dis+l);
		printf("Scenario #%d:\n",cas++);
		int index = ceil(l*p*1.0/100.0)-1;
		printf("%d\n\n",dis[index]);
	}
	return 0;
}