How to implement the fastest way to find the lengths of all shortest paths from one source node and detect negative cycles at the same time in C++?

Entire Problem I am trying to solve: Rich Cows.

Right now I have a problem that needs me to identify the shortest path from one node to all others using a given graph. Some details:

1. This is a weighted graph that can have both positive and negative edge lengths.
2. The source node is always 1.
3. There can be negative cycles in this graph.
4. The program is to output the string "-INFINITY" if that is the shortest path.

After some research on other questions, I settled on the Bellman-Ford algorithm. It was one of the only algorithms that could find negative cycles. However, some other questions do not answer mine either. For example: This one ignores negative cycles while this one deals with a python implementation, not the language I use, C++.

However, its time complexity did not meet the requirements. Is there any other way or algorithm that can perform the same calculations as my code below while working faster? Or is there any way to optimize Bellman-Ford and my code below? I am sure that the problem is the algorithm because I tested the times of the input, initialization, and output. They were all reasonably short.

My code is below. I tried to end the algorithm when it didn't change anything, along with the second run of it to find negative cycles. I also added lines like ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); However, while the changes were helpful, it didn't solve the problem. Can anybody help? Thanks in advance!

#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;
}

You are using std::deque rather than std::vector for trails and dist. Try switching to a std::vector.

Asymptotically this may be irrelevant since both are typically implemented using dynamic arrays; the operations on a std::deque have the same (or better, for operations which prepend or remove elements at the front) asymptotic time complexities.

A deque will however add overhead compared to just a vector since it has to support more operations efficiently; for example, I would assume that a deque needs to allocate free space on both ends, whereas for a vector free space on one end suffices.

In general, when implementing algorithms, try to be as frugal as possible: Use the simplest and most efficient (not just asymptotically) data structures. Appending to a linked list may have the same asymptotic (amortized) time complexity as appending to a std::vector, but due to allocation overhead, appending to a std::vector is usually more efficient (both memory- and speed-wise). Or, for another example: Augmenting a tree-based sorted set to hold ranks (counts) doesn't affect the time complexity either, but worsens the constant factors. If you don't need the ranks, use a sorted set which isn't augmented.