poj3615

floyd变形

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;

#define maxn 306
#define inf 0x3f3f3f3f

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

void input()
{
    scanf("%d%d%d", &n, &m, &t);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            map[i][j] = inf;
    for (int i = 0; i < m; i++)
    {
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        a--;
        b--;
        map[a][b] = w;
    }
}

void make()
{
    for (int k = 0; k < n; k++)
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
                map[i][j] = min(map[i][j], max(map[i][k], map[k][j]));
}

void work()
{
    for (int i = 0; i < t; i++)
    {
        int a, b;
        scanf("%d%d", &a, &b);
        a--;
        b--;
        if (map[a][b] == inf)
            printf("-1\n");
        else
            printf("%d\n", map[a][b]);
    }
}

int main()
{
    //freopen("t.txt", "r", stdin);
    input();
    make();
    work();
    return 0;
}