如何在C++中快速实现单源最短路径计算及负环检测？

我正在解决名为Rich Cows的问题，需要实现带权图的单源最短路径求解，具体需求如下：

• 图为带权图，边权可正可负
• 源节点固定为1
• 图中可能存在负环
• 若某节点的最短路径为负无穷，程序需输出字符串"-INFINITY"

我选择了Bellman-Ford算法，因为它是少数能检测负环的算法之一，但现有相关资料无法满足我的需求：要么忽略负环处理，要么是Python实现而非我使用的C++。

目前Bellman-Ford的时间复杂度达不到要求，我已经做了一些优化（比如无更新时提前终止、优化IO），但问题仍未解决，希望找到更快的替代算法，或者进一步优化Bellman-Ford的方法。

我的代码如下：

#include <iostream>
#include <deque>
struct Edge {
    long long from = 0;
    long long to = 0;
    long long weight = 0;
};
long long n = 0, m = 0;// n = number of vertices, m = number of edges
std::deque <Edge> trails; // collection of paths
std::deque <long long> dist; // the end result from the source to each of the other nodes
void bellmanford() { // part 1 of my goals
    dist[1] = 0; // set source to 0
    for (long long i = 0; i < n - 1; i++) {
        bool changed = false; // no change initially
        for (long long j = 0; j < m; j++) {
            if (dist[trails[j].to] > dist[trails[j].from] + trails[j].weight) { // check if its better than the previous path
                dist[trails[j].to] = dist[trails[j].from] + trails[j].weight; // update
                changed = true; // if something changes, we keep going because another change could happen
            }
        }
        if (changed == false) { return; } // if nothing occurs, more runs would be useless, so end
    }
}
void negativeCycleCatcher() { // part 2 of my goals
//this is pretty much the same thing as the bellmanford function except it changes nodes to -INFINITY
    for (long long i = 0; i < n - 1; i++) {
        bool changed = false;
        for (long long j = 0; j < m; j++) {
            if (dist[trails[j].to] > dist[trails[j].from] + trails[j].weight) {
                dist[trails[j].to] = -2147483647;
                changed = true;
            }
        }
        if (changed == false) { return; }
    }
}
int main () {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0), std::cout.tie(0);
    std::cin >> n >> m;
    trails.resize(m);
    dist.resize(n + 2, 2147483647); // initialize all distances with a large number
    for (long long i = 0; i < m; i++) { std::cin >> trails[i].from >> trails[i].to >> trails[i].weight; }
    bellmanford(); // find shortest paths
    negativeCycleCatcher(); // find negative cycles and nodes with -INFINITY
    for (long long i = 1; i <= n; i++) { // output results
        if (dist[i] == -2147483647) { std::cout << "-INFINITY"; }
        else { std::cout << dist[i]; }
        std::cout << '\n';
    }
    return 0;
}

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