Proficient.
Put your skills to the test.

Problem summary

A directed flight costs an integer number of credits, possibly zero or negative. A traveler may start at any vertex with 10⁵⁰ credits and must never have a negative balance. Determine whether a route of 10¹⁰⁰ flights exists; flights and vertices may repeat.

Constraints

1 ≤ N ≤ 5000; 1 ≤ M ≤ 2N; vertices are numbered 0 through N−1; −10⁹ ≤ C ≤ 10⁹; no loops or duplicate directed flights.

Worked example

An independently prepared example for this explanation.

6 7
0 1 -3
0 2 -5
0 4 0
1 2 -4
2 3 2
3 0 4
5 2 2

1

Solution analysis

1. The huge constants reduce the problem to the existence of a directed cycle of total cost at most zero. Such a cycle can be repeated forever: its internal cost fluctuations are tiny compared with 10⁵⁰. If every cycle has positive integer cost, every removed cycle consumes at least one credit, so even a route using the entire initial budget has far fewer than 10¹⁰⁰ edges.
2. First run Bellman–Ford with all distances initialized to zero, equivalent to adding a free super-source to every vertex. A strict relaxation in the N-th pass detects a negative cycle and immediately gives answer 1. Otherwise the distances are feasible potentials: every edge has nonnegative reduced cost C+dist[A]−dist[B].
3. A cycle has zero original cost exactly when its reduced costs sum to zero. Since all are nonnegative, every edge of such a cycle must have reduced cost zero. Build the subgraph of these tight edges and test it for a directed cycle using indegree elimination. In the first example, 0→1→2→3→0 has cost −1, so Bellman–Ford already proves that the trip can continue indefinitely.

Why it works

A nonpositive cycle is affordable with the initial balance because a simple cycle has at most N edges and its maximum internal deficit is at most N·10⁹. Repetition never decreases the balance over a full cycle. Conversely, remove simple cycles from any route. If all cycles cost at least one, and the remaining simple path costs at least −N·10⁹, at most 10⁵⁰+N·10⁹ cycles can occur; each has at most N edges, giving a bound far below 10¹⁰⁰. Bellman–Ford detects negative cycles. With none present, potential terms cancel around cycles, so the tight-edge cycle test detects exactly zero-cost cycles. These two tests therefore decide the necessary and sufficient condition.

Watch out. Strict Bellman–Ford relaxation finds negative cycles, not zero cycles. Starting vertices are unrestricted, so initialize every distance to zero. Use 64-bit potentials.

An independently written complete program with standard headers.

#include<iostream>
#include<queue>
#include<vector>
// Algorithm: The huge constants reduce the problem to the existence of a directed cycle of total
// cost at most zero.
using namespace std;
struct Edge{
    int from,to;
    long long cost;
};
int main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m;
    cin>>n>>m;
    vector<Edge>edges(m);
    for(Edge&edge:edges){
        cin>>edge.from>>edge.to>>edge.cost;
    }
    vector<long long>distance(n,0);
    for(int pass=0;pass<n;++pass){
        bool changed=false;
        for(Edge edge:edges){
            if(distance[edge.to]>distance[edge.from]+edge.cost){
                distance[edge.to]=distance[edge.from]+edge.cost;
                changed=true;
            }
        }
        if(!changed){
            break;
        }
        if(pass==n-1){
            cout<<"1\n";
            return 0;
        }
    }
    vector<vector<int>>tight(n);
    vector<int>indegree(n);
    for(Edge edge:edges){
        if(edge.cost+distance[edge.from]-distance[edge.to]==0){
            tight[edge.from].push_back(edge.to);
            ++indegree[edge.to];
        }
    }
    queue<int>ready;
    for(int vertex=0;vertex<n;++vertex){
        if(indegree[vertex]==0){
            ready.push(vertex);
        }
    }
    int removed=0;
    while(!ready.empty()){
        int vertex=ready.front();
        ready.pop();
        ++removed;
        for(int next:tight[vertex]){
            if(--indegree[next]==0){
                ready.push(next);
            }
        }
    }
    cout<<(removed<n?1:0)<<'\n';
}