Endless Fatigue Loop
- Memory limit
- 256 MB
- Correctness time limit
- 10000 ms
- Solvers
- 0
A maze has n rooms numbered 0 to n - 1 connected by one-way passages. edges[i] = [a, b, c] is a passage from
room a to room b that changes your fatigue by c (a negative c means you recover).
Return true if there is any cycle (a walk that returns to its starting room) whose total change is negative, so
that looping it lowers fatigue without bound; otherwise return false. The starting room can be any room.
Examples
| n | edges | result |
|---|---|---|
3 | [[0, 1, 4], [1, 2, -3], [2, 0, -2]] | true |
3 | [[0, 1, 4], [1, 2, -3], [2, 0, 1]] | false |
4 | [[0, 1, 1], [2, 3, -5], [3, 2, 4]] | true |
Example 3 — The cycle 2 → 3 → 2 (total -1) is not reachable from room 0, but any start is allowed.
Efficiency
This problem has performance tests. Judge the required time complexity from the input sizes in the constraints.
Function signature
solution(n: int, edges: int[][]) → bool
Constraints
-
n,edges.length -
a,b,c - Parallel passages and self-loops (
a = b) may appear.
Expected complexity
- Time
- O(N * M)
- Space
- O(N + M)
Examples
| n | edges | Expected |
|---|---|---|
3 | [[0,1,4],[1,2,-3],[2,0,-2]] | true |
3 | [[0,1,4],[1,2,-3],[2,0,1]] | false |
4 | [[0,1,1],[2,3,-5],[3,2,4]] | true |
Hint
Hint
Run Bellman–Ford with every dist starting at 0 (a virtual source connected to all rooms). Without a negative cycle,
nothing improves after rounds; if the -th round still relaxes an edge, a negative cycle exists. Stop early when a
round changes nothing. Floyd–Warshall () exceeds the time limit; is required.
Time limits per language
| Language | Efficiency time limit | |
|---|---|---|
| C (GCC, gnu17) | 200 ms | estimated |
| C++ (GCC, gnu++23) | 200 ms | derived |
| Python 3.13 | 1000 ms | derived |
| Java 25 | 1000 ms | derived |
| Kotlin 2.4 (JVM) | 1400 ms | estimated |
| C# 14 (.NET 10) | 1400 ms | estimated |
Test groups
| Group | Weight | Tests | Visibility |
|---|---|---|---|
| sample | 0 | 3 | inputs and outputs |
| correctness | 40 | 13 | verdict only |
| performance | 60 | 4 | verdict only |