题解：P12043 [USTCPC 2025] 图上交互题4 / Constructive Shortest Path

· · 题解

P12043 [USTCPC 2025] 图上交互题4 / Constructive Shortest Path 题解

题目传送门

题意简述

给定一个 n 个点、m 条边的无向图。每条边有一个未知的非负边权 a_i。题目同时给出了每条边 (u_i, v_i) 对应的最短路长度 f(u_i, v_i)。

我们需要判断是否存在一组合法的边权 a_i，使得对于题目给出的每一条边，其两端点的最短路长度恰好等于给定的 f(u_i, v_i)。如果存在，则输出任意一组构造方案。

算法介绍

本题的核心思路是利用最短路三角不等式进行约束检查与构造。

  1. 初始化最短路矩阵：我们首先用题目给定的 f(u_i, v_i) 作为点对 (u_i, v_i) 之间的初始距离，构建一个初始的距离矩阵 dist。对于没有直接给定距离的点对，距离设为无穷大（INF）。特别地，dist[i][i] = 0。

  2. Floyd-Warshall 算法求传递闭包：在初始矩阵上运行 Floyd-Warshall 算法。这步的目的是计算出在当前给定的“边权”下，所有点对之间的真正最短路。如果一条路径能够通过其他点中转，使得距离变得更短，那么 dist 矩阵会被更新。

  3. 合法性检查：算法结束后，我们检查每一条输入边 (u_i, v_i)。如果 dist[u_i][v_i] 小于 题目给定的 f(u_i, v_i)，这意味着存在一条比直接走这条边更短的路径。这与“f(u_i, v_i) 是这条边两端点的最短路”矛盾，因此无解，输出 No。

  4. 构造方案：如果所有边都通过了检查，那么直接将每条边的权值 a_i 赋值为题目给定的 f(u_i, v_i)，即可构造出一组合法解。

正确性证明

  1. 必要性：如果存在一组合法的边权 a_i，那么 Floyd-Warshall 算法求出的最短路矩阵 dist 一定满足 dist[u_i][v_i] ≤ f(u_i, v_i)。因为 f(u_i, v_i) 本身就是一条路径（即这条边本身）的长度。如果 dist 更小，则说明有更短路径，与 f(u_i, v_i) 是最短路的定义矛盾。因此，我们的检查步骤是必要的。

  2. 充分性：如果所有边都满足 dist[u_i][v_i] == f(u_i, v_i)，那么我们构造的边权 a_i = f(u_i, v_i) 一定是合法的。

    • 首先，对于输入中的任意一条边 e_i，其长度就是 f(u_i, v_i)。
    • 由于 Floyd-Warshall 已经求出了所有点对的最短路，且我们验证了 dist[u_i][v_i] 不大于任何给定的 f，因此不存在比 f(u_i, v_i) 更短的路径。
    • 所以，f(u_i, v_i) 确实是这条边两端点的最短路长度，构造合法。

  3. 时间复杂度：Floyd-Warshall 算法的时间复杂度为 O(n^3)，在 n \le 500 的数据范围下是可接受的。检查与构造的时间复杂度为 O(m)。

代码实现

#include <bits/stdc++.h>
using namespace std;

const long long INF = 4e18;
long long dist[505][505];
int n, m;

struct Edge {
    int u, v;
    long long d;
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            dist[i][j] = (i == j ? 0 : INF);
        }
    }

    vector<Edge> edges;
    bool ok = true;

    for (int i = 0; i < m; i++) {
        int u, v;
        long long d;
        cin >> u >> v >> d;
        edges.push_back({u, v, d});

        if (u == v) {
            if (d != 0) ok = false;
        } else {
            if (dist[u][v] == INF) {
                dist[u][v] = dist[v][u] = d;
            } else if (dist[u][v] != d) {
                ok = false;
            }
        }
    }

    if (!ok) {
        cout << "No\n";
        return 0;
    }

    for (int k = 1; k <= n; k++) {
        for (int i = 1; i <= n; i++) {
            if (dist[i][k] == INF) continue;
            for (int j = 1; j <= n; j++) {
                if (dist[k][j] == INF) continue;
                long long nd = dist[i][k] + dist[k][j];
                if (nd < dist[i][j]) dist[i][j] = nd;
            }
        }
    }

    for (auto &e : edges) {
        if (dist[e.u][e.v] != e.d) {
            cout << "No\n";
            return 0;
        }
    }

    cout << "Yes\n";
    for (int i = 0; i < m; i++) {
        if (i) cout << ' ';
        cout << edges[i].d;
    }
    cout << '\n';

    return 0;
}

给过吧喵 洛谷将流芳百世