3576985_ac_500ms_560k.cpp

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

#include <stdio.h>
#include <string.h>

int map[300][300];
int n, m, t;

int max(int a, int b)
{
	return a > b ? a : b;
}

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

int main()
{
	int i, a, b, c;

	memset(map, 0, sizeof(map));
	scanf("%d%d%d", &n, &m, &t);
	for (i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		a--;b--;
		map[a][b] = max(map[a][b], c);
	}
	floyd();
	for (i = 0; i < t; i++)
	{
		scanf("%d%d", &a, &b);
		a--;b--;
		if (map[a][b] == 0)
			puts("-1");
		else
			printf("%d\n", map[a][b]);
	}
	return 0;
}