我的Ford-Bellman算法实现问题：最长路径求解测试未通过

给定一个边权可负的有向加权图，求从第一个顶点到最后一个顶点的最长路径长度，规则如下：

• 若不存在该路径，输出:(；
• 若路径长度无限长，输出:)。

我的代码在22个测试用例中通过了21个，但无法定位失败的测试用例。已知失败的测试用例正确答案是:)——提交一个始终输出:)的程序时通过了该用例，但其他大量用例未通过，说明问题出在判断输出:)的逻辑部分。

补充说明：题目保证1≤n≤2000，1≤m≤10000，无法访问测试用例。

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Node
{
    int val = 0;
    bool isNull = true;
};

struct Edge
{
    int from;
    int to;
    int cost;
};

int main()
{
    int n, m;
    cin >> n >> m;

    vector<Node> nodes(n);
    vector<Edge> edges(m);

    for (int i = 0; i < m; i++)
    {
        int from, to, cost;
        cin >> from >> to >> cost;
        edges[i] = { from - 1, to - 1, cost };
    }
    nodes[0].val = 0;
    nodes[0].isNull = false;

    for (int i = 0; i < max(nodes.size() - 1, (vector<Node>::size_type)1); i++)
    {
        for (auto [from, to, cost] : edges)
        {
            if (!nodes[from].isNull && (nodes[to].isNull || nodes[to].val < nodes[from].val + cost))
            {
                nodes[to].isNull = false;
                nodes[to].val = nodes[from].val + cost;
            }
        }
    }

    if (nodes.back().isNull)
    {
        cout << ":(";
        return 0;
    }

    for (auto [from, to, cost] : edges)
    {
        if (!nodes[from].isNull && nodes[to].val < nodes[from].val + cost)
        {
            for (int i = 0; i < max(nodes.size() - 1, (vector<Node>::size_type)1); i++)
            {
                for (auto [from, to, cost] : edges)
                {
                    if (!nodes[from].isNull && nodes[to].val < nodes[from].val + cost)
                    {
                        if (to == nodes.size() - 1)
                        {
                            cout << ":)";
                            return 0;
                        }

                        nodes[to].val = nodes[from].val + cost;
                    }
                }
            }
        }
    }

    cout << nodes.back().val;

    return 0;
}

你的代码在判断“是否存在导致终点最长路径无限长的正环”时逻辑存在漏洞，具体问题如下：

1. 正环检测范围错误
   你当前的逻辑是：发现可松弛的边后，重新跑n-1轮松弛，仅当某次松弛直接作用到终点时才输出:)。但实际上，只要存在从起点可达、且能到达终点的正环（权值和为正的环），终点的最长路径就是无限长的——因为可以绕环无限次累加路径长度，再走到终点。你的代码忽略了“正环不在终点直接前驱路径上，但环的节点能到达终点”的场景，会漏判这类情况。

2. 冗余且不准确的松弛过程
   重新跑n-1轮松弛的做法完全没必要，且无法覆盖所有需要判定的场景。正确的检测逻辑应该是：

   • 用Bellman-Ford算法跑n-1轮松弛，得到起点到各节点的最长路径；
   • 再跑1轮松弛，标记所有仍可被松弛的节点（这些节点要么在正环内，要么能到达正环）；
   • 通过BFS/DFS判断这些标记节点中是否存在能到达终点的节点，若存在则输出:)。

1. 替换Node结构体为普通距离数组，用极小值（如-1e18）表示不可达，避免isNull判断的潜在问题；
2. 完成Bellman-Ford的n-1轮松弛后，标记所有可继续松弛的节点；
3. 通过邻接表+BFS/DFS，判断标记节点能否到达终点；
4. 根据终点的可达性、是否存在上述正环，输出对应结果。

核心修正逻辑示例：

vector<long long> dist(n, -1e18);
dist[0] = 0;

// Bellman-Ford n-1轮松弛
for (int i = 0; i < n-1; ++i) {
    bool updated = false;
    for (auto &e : edges) {
        if (dist[e.from] != -1e18 && dist[e.to] < dist[e.from] + e.cost) {
            dist[e.to] = dist[e.from] + e.cost;
            updated = true;
        }
    }
    if (!updated) break; // 提前终止无更新的轮次
}

// 标记所有可继续松弛的节点（正环或正环可达节点）
vector<bool> is_infinite(n, false);
for (auto &e : edges) {
    if (dist[e.from] != -1e18 && dist[e.to] < dist[e.from] + e.cost) {
        is_infinite[e.to] = true;
    }
}

// 构建邻接表，BFS判断标记节点能否到达终点
vector<vector<int>> adj(n);
for (auto &e : edges) {
    adj[e.from].push_back(e.to);
}

vector<bool> visited(n, false);
queue<int> q;
for (int i = 0; i < n; ++i) {
    if (is_infinite[i]) {
        q.push(i);
        visited[i] = true;
    }
}

while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int v : adj[u]) {
        if (!visited[v]) {
            visited[v] = true;
            q.push(v);
        }
    }
}

// 输出结果
if (dist[n-1] == -1e18) {
    cout << ":(" << endl;
} else if (visited[n-1]) {
    cout << ":)" << endl;
} else {
    cout << dist[n-1] << endl;
}

内容的提问来源于stack exchange，提问作者Roman Leshchuk