Floyd 预处理

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
const int INF = 2147483647;
int n, m, T;
int e[MAXN + 5][MAXN + 5];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> T;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            e[i][j] = INF;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u][v] = w;
    }
    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                if (e[i][k] != INF && e[k][j] != INF)
                    e[i][j] = min(e[i][j],
                                  max(e[i][k], e[k][j]));
    while (T--)
    {
        int st, ed;
        cin >> st >> ed;
        if (e[st][ed] == INF)
            cout << -1 << "\n";
        else
            cout << e[st][ed] << "\n";
    }
    return 0;
}

Dijkstra 预处理

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 300;
const int INF = 2147483647;
int n, m, T;
vector<pair<int, int>> e[MAXN + 5];
int dis[MAXN + 5][MAXN + 5];
bool vis[MAXN + 5][MAXN + 5];
priority_queue<pair<int, int>> pq;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> T;
    for (int i = 1; i <= m; i++)
    {
        int u, v, w;
        cin >> u >> v >> w;
        e[u].push_back(make_pair(v, w));
    }
    for (int s = 1; s <= n; s++)
    {
        for (int i = 1; i <= n; i++)
            dis[s][i] = INF;
        dis[s][s] = 0;
        pq.push(make_pair(-dis[s][s], s));
        while (!pq.empty())
        {
            int u = pq.top().second;
            pq.pop();
            if (vis[s][u])
                continue;
            for (int i = 0; i < e[u].size(); i++)
            {
                int v = e[u][i].first;
                int w = e[u][i].second;
                if (max(dis[s][u], w) < dis[s][v])
                {
                    dis[s][v] = max(dis[s][u], w);
                    pq.push(make_pair(-dis[s][v], v));
                }
            }
        }
    }
    while (T--)
    {
        int st, ed;
        cin >> st >> ed;
        if (dis[st][ed] == INF)
            cout << -1 << "\n";
        else
            cout << dis[st][ed] << "\n";
    }
    return 0;
}