atcoder_mindist.rs

#[derive(Eq, PartialEq,)]
struct Item{
    dist: INF64,
    pos: usize
}

impl Ord for Item {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        if self.dist < other.dist{
            std::cmp::Ordering::Greater
        }else if self.dist > other.dist{
            std::cmp::Ordering::Less
        }else{
            std::cmp::Ordering::Equal
        }
    }
}

impl PartialOrd for Item{
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

fn calc_mindist(starting: usize, n: usize, conn: &Vec<Vec<usize>>) -> Vec<INF64>{
    let mut visited = vec![false; n];
    let mut pending = BinaryHeap::new();
    pending.push(Item{dist: INF64::Raw(0), pos: starting});
    let mut dists = vec![InfNum::<i64>::PosInf; n];

    while !pending.is_empty(){
        let popped = pending.pop().unwrap();

        if visited[popped.pos]{
            continue;
        }

        visited[popped.pos] = true;
        dists[popped.pos] = popped.dist.clone();

        for i in &conn[popped.pos.clone()]{
            pending.push(Item{dist: popped.dist.clone() + InfNum::Raw(1), pos: *i})
        }
    }

    return dists;
}