个人简介

我是 xhgua，ZJ 高一 OIer。

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e5 + 5, INF = (1 << 30);

int n, m, k;
bool vis[N];
int dis1[N], dis2[N];
std::vector<std::pair<int, int>> G1[N], G2[N];

int main() {

    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::cin >> n >> m >> k;
    for (int i = 1; i <= m; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        G1[v].push_back({u, w});
    }
    for (int i = 1; i <= k; i++) {
        int u, v, w;
        std::cin >> u >> v >> w;
        G2[v].push_back({u, w});
    }

    std::priority_queue<std::pair<int, int>> q;
    q.push({0, 0});

    for (int i = 0; i <= n; i++) dis1[i] = INF, vis[i] = false;
    dis1[0] = 0;

    while (!q.empty()) {
        int u = q.top().second; q.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (auto e : G1[u]) {
            int v = e.first, w = e.second;
            if (dis1[u] + w < dis1[v]) {
                dis1[v] = dis1[u] + w;
                q.push({-dis1[v], v});
            }
        }
    }

    q.push({0, 0});

    for (int i = 0; i <= n; i++) dis2[i] = INF, vis[i] = false;
    dis2[0] = 0;

    while (!q.empty()) {
        int u = q.top().second; q.pop();

        if (vis[u]) continue;
        vis[u] = true;

        for (auto e : G2[u]) {
            int v = e.first, w = e.second;
            if (dis2[u] + w < dis2[v]) {
                dis2[v] = dis2[u] + w;
                q.push({-dis2[v], v});
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= n; i++) ans = std::max(ans, std::min(dis1[i], dis2[i]));

    std::cout << ans << "\n";

    return 0;
}