This is a problem I came up with while thinking about cycle-based optimization on graphs. I'm not sure if it's well-known or if I'm missing something obvious, either way I couldn't solve it, so I'd love to hear how more experienced people would approach it.
Problem Statement
You are given a directed graph with N nodes and M edges. It may have self-loops and multiple edges between the same pair of nodes.
Each edge is described by three integers u, v, w:
- you can move from node u to node v
- the move takes exactly 1 unit of time
- you gain w coins after using this edge
You start at node 1 with 0 coins. You may traverse any edge any number of times and revisit nodes freely.
Find the minimum time to collect at least K coins. If it is impossible, print -1.
Examples
Example 1
Input:
5 6 24
1 2 6
2 1 6
1 3 0
3 4 8
4 5 8
5 3 7
Output:
4
Example 2
Input:
5 6 31
1 2 6
2 1 6
1 3 0
3 4 8
4 5 8
5 3 7
Output:
5
Constraints
$$$1 \le N, M \le 2 \cdot 10^5$$$
$$$1 \le K \le 10^{18}$$$
$$$w \ge 0$$$
Why I Find This Hard
The tricky part is that the best strategy is not fixed, it depends on K:
- Some cycles have great coins/move ratio but are expensive to reach
- Others are easy to enter but scale worse
- K can be up to $$$10^{18}$$$ , so any DP over coins is completely out
My rough instinct says it involves some mix of:
- SCC condensation: collapsing strongly connected components
- Cycle profit analysis: finding the highest coins-per-time ratio cycle reachable from node 1
- Shortest-path reasoning: accounting for the "entry cost" to reach each cycle
- Binary search on time: fix T, ask if we can collect K coins in T steps
But I can't figure out how to tie these together cleanly, especially when multiple cycles compete and the answer shifts with K.
What I'm Looking For
Would really appreciate insight on any of these:
- What is the key observation that simplifies this?
- Is SCC decomposition actually necessary, or is there a cleaner framing?
- How do you reason about which cycle to "commit to" for a given K?
- Does this resemble any known classical problem?
Even a rough direction or a pointer to a similar problem would help a lot. Thanks!
