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!
Auto comment: topic has been updated by uday (previous revision, new revision, compare).
you can probably do something like matrix multiplication-like dp and binary search on answer. if you dont know the concept , check "counting length k paths in a graph"
This problem is NP-hard
Reduce Hamiltonian Path to this.
Split every vertex $$$v$$$ into $$$v_{in}, v_{out}$$$ where you earn 1 dollar for taking the edge $$$v_{in} \rightarrow v_{out}$$$. All other edges $$$u \rightarrow w$$$ connect $$$u_{out} \rightarrow w_{in}$$$ and pay you 0 dollars.
Now, a Hamiltonian Path exists iff you can collect $$$n$$$ dollars (by visiting every vertex) in $$$2n - 1$$$ edges ($$$n$$$ edges inside vertices, $$$n-1$$$ edges connecting vertices).
Edit: if visiting an edge a second time earns you the money a second time then I think you can do it with matrix multiplication like FatihCihan said. (but that will be like $$$n^3 \log n$$$)
This problem is not NP-hard, this solution have some polynomial solutions, but I don't think there are solution that satisfies the problem statement.