Find minimum cycle cost per node
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Take-home Project
## Problem
You are given a **weighted directed graph** with `n` nodes labeled `0..n-1` and `m` directed edges. Each edge is `(u, v, w)` meaning you can go from `u` to `v` with cost `w`.
For **each node `s`**, compute the **minimum total weight** of any path that:
- starts at `s`,
- follows directed edges,
- and eventually returns to `s` (i.e., forms a directed cycle starting/ending at `s`).
If it is **impossible** to return to `s`, output `0` for that node.
### Input
- Integers `n, m`
- `m` edges `(u, v, w)`
### Output
- An array `res` of length `n`, where `res[s]` is the minimum cycle cost starting/ending at `s`, or `0` if none exists.
### Constraints (typical for an OA)
- `1 <= n <= 2e5`
- `0 <= m <= 2e5`
- `1 <= w <= 1e9`
### Example
If edges are: `(0,1,5)`, `(1,0,2)`, `(1,2,1)`, `(2,1,1)` then:
- For `s=0`, min cycle is `0->1->0` cost `7`.
- For `s=2`, min cycle is `2->1->2` cost `2`.
Quick Answer: This question evaluates proficiency in graph algorithms and algorithmic optimization, specifically reasoning about weighted directed graphs, cycle costs, and shortest-path computations.
For every node, return the minimum positive-weight directed cycle cost starting and ending at that node, or 0 if none exists.
Constraints
- edge weights are positive
Examples
Input: (3, [(0, 1, 5), (1, 0, 2), (1, 2, 1), (2, 1, 1)])
Expected Output: [7, 2, 2]
Explanation: Example graph.
Input: (3, [(0, 1, 4), (1, 2, 5)])
Expected Output: [0, 0, 0]
Explanation: No cycles.
Input: (2, [(0, 0, 7), (0, 1, 1), (1, 0, 2)])
Expected Output: [3, 3]
Explanation: Self-loop can be best.
Hints
- Run shortest paths from s, then close the cycle through an incoming edge to s.