3577010_ac_610ms_612k.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 62 行

#include <stdio.h>

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

inline 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 = map[i][k] > map[k][j] ? 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;

	scanf("%d%d%d", &n, &m, &t);
	for (a = 0; a < n; a++)
	{
		for (b = 0; b < n; b++)
		{
			map[a][b] = 0;
		}
	}
	for (i = 0; i < m; i++)
	{
		scanf("%d%d%d", &a, &b, &c);
		map[a-1][b-1] = 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;
}