POJ 3615 牛的最小最大起跳高度问题 Floyd算法的变形应用

此题求牛从起点到终点路径中最大权值最小的那条路径，将Floyd算法稍作修改即可，注意此题输入输出处理不当可能引起超时，一般scanf及printf更节省时间。

#include <iostream>
#include <cstdio>
#define MAX_VEX 305
#define MAX_WEI 1000005
using namespace std;
int A[MAX_VEX][MAX_VEX];
//用cin,cout会超时
int main(){
	int N,M,T,i,j,k,h;
	int s,e,w;
	//cin>>N>>M>>T;
	scanf("%d%d%d",&N,&M,&T);
	for (i = 1;i <= N;i++)
		for (j = 1;j <= N;j++)
		{
			A[i][j] = MAX_WEI;
		}
	for (i = 0; i < M;i++)
	{
		//cin>>s>>e>>w;
		scanf("%d%d%d",&s,&e,&w);
		A[s][e] = w;
	}
	//关键代码部分
	for (i = 1;i <= N;i++)
		for (j = 1;j <= N;j++){
			if (A[j][i] == MAX_WEI)
				continue;//i,j之间不可直达
			for (k = 1;k <= N;k++){
				if (A[i][k] == MAX_WEI) continue;
				h = A[j][i] > A[i][k]?A[j][i]:A[i][k];
				if(h < A[j][k]) A[j][k] = h;
			}
		}
	for (i = 0;i < T;i++){
		//cin>>s>>e;
		scanf("%d%d",&s,&e);
		if (A[s][e] == MAX_WEI) //cout<<"-1"<<endl;
		printf("-1/n");
		else //cout<<A[s][e]<<endl;
		printf("%d/n",A[s][e]);
	}
	return 0;
}