floyd变形
View Code #include#include #include #include using namespace std;#define maxn 306#define inf 0x3f3f3f3fint 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;}