补全：INF 取多大才不溢出

👁️ 1 人浏览 💬 0 人评论 ❤️ 添加收藏

这段 Bellman-Ford 用 int 存距离，INF 取了 INT_MAX。从走不到的点松弛出去时，INF + w 会溢出成负数（有符号溢出是未定义行为，本平台 g++ 实际会变成负数），把走不到的点也改成了负数。补全 INF 的取值，输出距离表（走不到的写 -1）。

（本题用 g++ -std=c++17 -O0 编译。）

提交你的答案

请登录后提交答案。

去登录

← 补全：跳过过期的堆元素补全：距离用 long long →

更多题目

代码编辑器

语言： Ctrl + Enter 运行

#include <algorithm>
#include <iostream>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

typedef long long ll;
const ll INF = 1000000000;                       // 走不到的点记这个值，输出时写成 -1
using Graph = vector<vector<pair<int, int>>>;    // g[u] 里放 (邻居 v, 边权 w)

#include <climits>

const int INF_I = INT_MAX;   // TODO: INF + w 会溢出，换一个相加也不溢出的取值

string show_i(const vector<int>& d) {
    string s;
    for (size_t i = 0; i < d.size(); i++) s += (i ? "/" : "") + (d[i] >= INF_I ? string("-1") : to_string(d[i]));
    return s;
}

vector<int> bellman_i(const vector<vector<pair<int, int>>>& g, int s) {
    int n = g.size();
    vector<int> d(n, INF_I);
    d[s] = 0;
    for (int round = 0; round < n - 1; round++) {
        for (int u = 0; u < n; u++) {
            for (auto [v, w] : g[u]) {
                if (d[u] + w < d[v]) d[v] = d[u] + w;
            }
        }
    }
    return d;
}

int main() {
    // 0→1:5；3 号走不到，但它有一条 3→2:7 的边
    vector<vector<pair<int, int>>> g = {{{1, 5}}, {}, {}, {{2, 7}}};
    cout << show_i(bellman_i(g, 0)) << endl;
}

本次输入：

输出：

👩‍🏫

💬 题目评论

补全：INF 取多大才不溢出

更多题目

全部评论