I wrote an algorithm (bidirectional Dijkstra algorithm for undirected graph) with both of Rust and C++ to solve this problem. In short: You are given a simple undirected graph G. Calculate the radius of G.

Rust version gives correct output, but runs much slower than C++ with some test cases.

Rust (4659 ms maximum) : https://beta.atcoder.jp/contests/abc012/submissions/2282548

C++ (996 ms maximum) : https://beta.atcoder.jp/contests/abc012/submissions/2281364

I believe that the bottleneck is function `bidirectional_dijkstra`

pasted bellow:

```
/// Pair of (id of vertex) and (distance to there)
#[derive(PartialEq, Eq, Clone, Copy)]
struct DijkstraState(usize, Weight);
/// Reverse order of distance
impl Ord for DijkstraState {
fn cmp(&self, other: &DijkstraState) -> Ordering {
other.1.cmp(&self.1)
}
}
impl PartialOrd for DijkstraState {
fn partial_cmp(&self, other: &DijkstraState) -> Option<Ordering> {
Some(self.cmp(other))
}
}
/// Find the distance between `src` and `dst` on `graph`.
/// Returns `Some(value)` if reachable and the distance is `value`, `None` otherwise.
pub fn bidirectional_dijkstra(graph: &Graph, src: usize, dst: usize) -> Option<Weight> {
if src == dst {
Some(0)
} else {
let inf: Weight = Weight::max_value() / 2;
let n = graph.len();
// heap from `src`
let mut heaps = BinaryHeap::with_capacity(n);
// heap from `dst`
let mut heapd = BinaryHeap::with_capacity(n);
heaps.push(DijkstraState(src, 0));
heapd.push(DijkstraState(dst, 0));
// distance table from `src`
let mut dists = vec![inf; n];
// distance table from `dst`
let mut distd = vec![inf; n];
dists[src] = 0;
distd[dst] = 0;
// upper bound of return value
let mut mu = inf;
while let Some((DijkstraState(v, d), heap, dist, dist_)) = {
let DijkstraState(_, ds) = *heaps.peek().unwrap_or(&DijkstraState(n, inf));
let DijkstraState(_, dd) = *heapd.peek().unwrap_or(&DijkstraState(n, inf));
if ds + dd >= mu {
// optimal value which can be obtained in future is greater than or equal to mu,
// so break loop.
None
} else if ds <= dd {
// update from `src`-side
heaps.pop().map(|x| (x, &mut heaps, &mut dists, &mut distd))
} else {
// update from `dst`-side
heapd.pop().map(|x| (x, &mut heapd, &mut distd, &mut dists))
}
} {
// update around `v` if optimal distance to v equals to d
if dist[v] == d {
// iterate vertices adjacent to `v`
for e in graph[v].iter() {
if dist[e.dst] > d + e.weight {
dist[e.dst] = d + e.weight;
heap.push(DijkstraState(e.dst, dist[e.dst]));
mu = min(mu, dist[e.dst] + dist_[e.dst]);
}
}
}
}
if mu != inf {
Some(mu)
} else {
None
}
}
}
```

Do you have any idea to speed up this?

I know that there are more efficient ways to solve the problem, but I simply hope to know why this code is slow.

Thank you.