POJ 3615 Cow Hurdles

ワーシャルフロイド

ソースコード

int main()
{
    int n, m, t;
    scanf("%d%d%d", &n, &m, &t);
    const int inf = ten(8);
    int w[303][303];
    rep(i, n) rep(j, n)
	w[i][j] = i == j ? 0 : inf;
    while (m--)
    {
	int s, e, h;
	scanf("%d%d%d", &s, &e, &h);
	--s, --e;
	w[s][e] = h;
    }

    rep(k, n) rep(i, n) rep(j, n)
	chmin(w[i][j], max(w[i][k], w[k][j]));

    while (t--)
    {
	int a, b;
	scanf("%d%d", &a, &b);
	--a, --b;
	printf("%d\n", w[a][b] == inf ? -1 : w[a][b]);
    }
}