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↵
```↵
↵
<spoiler summary="Explanation">↵
Two useful cycles exist:↵
↵
**Cycle A:** `1 → 2 → 1` takes 2 moves and gives 12 coins per loop.↵
↵
**Cycle B:** once you reach node 3, the loop `3 → 4 → 5 → 3` takes 3 moves and gives 23 coins.↵
↵
For K = 24, looping Cycle A twice gives exactly 24 coins in 4 moves. Cycle B requires travel time to node 3 before it even starts, so it's slower here.↵
</spoiler>↵
↵
---↵
↵
### 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↵
```↵
↵
<spoiler summary="Explanation">↵
With Cycle A: after 5 moves you only have 30 coins, and after 6 you'd have 36 — that's 6 moves total, too slow.↵
↵
But going `1 → 3 → 4 → 5 → 3 → 4` collects 0 + 8 + 8 + 7 + 8 = 31 coins in exactly 5 moves.↵
↵
So for larger K, Cycle B becomes the better choice.↵
</spoiler>↵
↵
---↵
↵
## 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!
↵
---↵
↵
## 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↵
```↵
↵
<spoiler summary="Explanation">↵
Two useful cycles exist:↵
↵
**Cycle A:** `1 → 2 → 1` takes 2 moves and gives 12 coins per loop.↵
↵
**Cycle B:** once you reach node 3, the loop `3 → 4 → 5 → 3` takes 3 moves and gives 23 coins.↵
↵
For K = 24, looping Cycle A twice gives exactly 24 coins in 4 moves. Cycle B requires travel time to node 3 before it even starts, so it's slower here.↵
</spoiler>↵
↵
---↵
↵
### 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↵
```↵
↵
<spoiler summary="Explanation">↵
With Cycle A: after 5 moves you only have 30 coins, and after 6 you'd have 36 — that's 6 moves total, too slow.↵
↵
But going `1 → 3 → 4 → 5 → 3 → 4` collects 0 + 8 + 8 + 7 + 8 = 31 coins in exactly 5 moves.↵
↵
So for larger K, Cycle B becomes the better choice.↵
</spoiler>↵
↵
---↵
↵
## 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!
