POJ 3615 Cow Hurdles

問題文
http://poj.org/problem?id=3615

ワーシャルフロイド法をちょっとだけいじる。
N <= 300より、O(N^3)でも間に合う。
iostreamを使うとTLEした。

#include <cstdio>

using namespace std;
const int INF = 100000000;
int n,m,t;
int d[305][305];

int main(){

	for(int i = 0;i <= 303;i++){
		for(int j = 0;j <= 303;j++){
			if(i == j)continue;
			d[i][j] = INF;
		}
	}
	scanf("%d%d%d",&n,&m,&t);
	while(m--){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		d[a][b] = c;
	}

	for(int k = 1;k <= n;k++){
		for(int i = 1;i <= n;i++){
			for(int j = 1;j <= n;j++){
				d[i][j] = min(d[i][j],max(d[i][k],d[k][j]));
			}
		}
	}

	while(t--){
		int a,b;
		scanf("%d%d",&a,&b);
		if(d[a][b] == INF){
			printf("-1\n");
		}else{
			printf("%d\n",d[a][b]);
		}
	}
	return 0;
}