> will require reference counting
or use an arena (or backing store of handles, or graph of indices, or ...); which is basically the same situation as doing it in C unsafely with more or less the same cost.
> but only on a subset of algorithms that are valid in idiomatic Rust
IME almost all algorithms can be implemented in safe Rust, just that it takes some work to make it safe (e.g. using an arena, or shuffling some code around). The "limitations" of the borrow checker, for example (where it might be considered overzealous) can always be worked around by twiddling a few lines of code.
If it really comes to that (it shouldn't), you can always make your algorithm work with a few lines of unsafe Rust, and verify that locally. Still better than the entire thing being unsafe.
Regarding the 50% more effort to develop, we've gotten consistent feedback that the effort involved in writing Rust code is not more than any other typed language once you internalize some of its rules (which takes some time, but not too much).