Funcia
Lv.3bellman-fordgraphshortest-path

Endless Fatigue Loop

Memory limit
256 MB
Correctness time limit
10000 ms
Solvers
0
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

nedgesresult
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

  • 1≤1 \le n ≤1,000\le 1{,}000, 0≤M=0 \le M = edges.length ≤4,000\le 4{,}000
  • 0≤0 \le a, b <n< n, −106≤-10^6 \le c ≤106\le 10^6
  • Parallel passages and self-loops (a = b) may appear.

Expected complexity

Time
O(N * M)
Space
O(N + M)

Examples

nedgesExpected
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 n−1n - 1 rounds; if the nn-th round still relaxes an edge, a negative cycle exists. Stop early when a round changes nothing. Floyd–Warshall (O(n3)O(n^3)) exceeds the time limit; O(n⋅M)O(n \cdot M) is required.

Time limits per language

LanguageEfficiency time limit
C (GCC, gnu17)200 msestimated
C++ (GCC, gnu++23)200 msderived
Python 3.131000 msderived
Java 251000 msderived
Kotlin 2.4 (JVM)1400 msestimated
C# 14 (.NET 10)1400 msestimated

Test groups

GroupWeightTestsVisibility
sample03inputs and outputs
correctness4013verdict only
performance604verdict only
Loading editor…
Log in to run or submit code.

No result yet. Run or submit your code.