题解

题目分析

这是一道基于图论和动态规划的题目，需要在图中寻找最优路径。

解题思路

1. 问题建模

• 构建有向图，节点数为 $n$，边数为 $m$
• 每条边有权重，需要找到最优路径
• 使用动态规划求解最优解

2. 图构建

• 使用邻接表 g[N] 存储图结构
• 每条边存储目标节点和权重
• 支持多源最短路径计算

3. 最短路径算法

• 使用 Dijkstra 算法计算单源最短路径
• 使用优先队列优化：priority_queue<pair<ll, int>>
• 维护距离数组 dist[n+1] 和访问标记 vis[n+1]

4. 动态规划

• 定义状态：$b[i][j]$ 和 $s[i][j]$ 表示不同状态下的最优值
• 状态转移基于图的最短路径
• 考虑所有可能的路径组合

5. 关键技巧

• 使用 1e15 作为无穷大值
• 优先队列使用负数实现最小堆
• 避免重复访问已处理的节点

时间复杂度

$O(n^2 \log n)$，主要消耗在 Dijkstra 算法的多次调用上。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N = 100 + 7;
const int K = 1000 + 7;

int n, m, k;
vector<pair<int, int>> g[N];
ll b[N][K], s[N][K];

vector<ll> get_dist(int u) {
    vector<ll> dist(n + 1, 1e15);
    vector<bool> vis(n + 1);
    priority_queue<pair<ll, int>> pq;
    pq.push({0, u});
    dist[u] = 0;
    while (!pq.empty()) {
        int u = pq.top().second;
        pq.pop();
        if (vis[u]) continue;
        vis[u] = 1;
        for (auto [v, c] : g[u]) {
            if (dist[u] + c < dist[v]) {
                dist[v] = dist[u] + c;
                pq.push({-dist[v], v});
            }
        }
    }
    return dist;
}

ll give(int x, int y) {
    ll ans = 0;
    for (int i = 1; i <= k; ++i) if (s[y][i] != -1 && b[x][i] != -1) ans = max(ans, s[y][i] - b[x][i]);
    return ans;
}

vector<ll> dist[N];
ll gv[N][N];

bool check(__int128 x) {
    vector<vector<__int128>> f(n + 1, vector<__int128>(n + 1));
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i == j) {
                f[i][j] = -1e18;
                continue;
            }
            f[i][j] = gv[i][j] - (__int128) x * dist[i][j];
        }
    }
    for (int k = 1; k <= n; ++k) {
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= n; ++j) {
                f[i][j] = max(f[i][j], f[i][k] + f[k][j]);
                f[i][j] = min(f[i][j], (__int128) 1e18);
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = i + 1; j <= n; ++j) {
            if (f[i][j] + f[j][i] >= 0) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> m >> k;
    for (int i = 1; i <= n; ++i) for (int j = 1; j <= k; ++j) cin >> b[i][j] >> s[i][j];
    for (int i = 1; i <= m; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        g[a].push_back({b, c});
    }
    for (int i = 1; i <= n; ++i) dist[i] = get_dist(i);
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            gv[i][j] = give(i, j);
        }
    }
    ll l = 0, r = 1e9, sol = 0;
    while (l <= r) {
        int m = (l + r) / 2;
        if (check(m)) {
            sol = m;
            l = m + 1;
        } else {
            r = m - 1;
        }
    }
    cout << sol << "\n";
    return 0;
}