Leetcode1584 in rust

help
1 
use std::cmp::Reverse;
use std::collections::{BinaryHeap, HashMap,HashSet};
use std::{rc::Rc, cell::RefCell};
use std::hash::Hash;

#[derive(Debug)]
pub struct GraphNode {
    pub value: i32,
    pub in_degree: i32,
    pub out_degree: i32,
    pub nexts: Vec<i32>,
    pub edges: Vec<(usize, usize, i32)>,
}

impl GraphNode {
    pub fn new(value: i32) -> Rc<RefCell<GraphNode>> {
        Rc::new(RefCell::new(GraphNode {
            value,
            in_degree: 0,
            out_degree: 0,
            nexts: Vec::new(),
            edges: Vec::new(),
        }))
    }
}

#[derive(Debug, Eq)]
pub struct Edge {
    pub weight: i32,
    pub from_id: i32,
    pub to_id: i32,
}

impl PartialEq for Edge {
    fn eq(&self, other: &Self) -> bool {
        self.weight == other.weight && self.from_id == other.from_id && self.to_id == other.to_id
    }
}

impl Ord for Edge {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.weight.cmp(&other.weight)
    }
}

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

impl Hash for Edge {
    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
        self.weight.hash(state);
        self.from_id.hash(state);
        self.to_id.hash(state);
    }
}

#[derive(Debug)]
pub struct Graph {
    pub nodes: HashMap<i32, Rc<RefCell<GraphNode>>>,
    pub edges: HashSet<Edge>,
}

impl Graph {
    pub fn new() -> Self {
        Graph {
            nodes: HashMap::new(),
            edges: HashSet::new(),
        }
    }
}


impl Solution {
    pub fn min_cost_connect_points(points: Vec<Vec<i32>>) -> i32 {
        let n = points.len();
        let graph = Self::create_graph(points);
        let mut visited = vec![false; n];
        let mut min_heap = BinaryHeap::new();
        let mut total_cost = 0;

        min_heap.push(Reverse((0, 0)));

        while let Some(Reverse((node, cost))) = min_heap.pop() {
            if visited[node] {
                continue;
            }

            visited[node] = true;
            total_cost += cost;

            let from = graph.nodes.get(&(node as i32)).unwrap();
            for (_, to, weight) in from.borrow().edges.iter() {
                min_heap.push(Reverse((*to, *weight)));
            }
        }

        total_cost
    }

    fn create_graph(points: Vec<Vec<i32>>) -> Graph {
        let mut graph = Graph::new();

        for from in 0..points.len() {
            let new_node = GraphNode::new(0);
            for to in from + 1..points.len() {
                new_node.borrow_mut().edges.push((
                    from,
                    to,
                    Self::manhattan_distance(&points[from], &points[to]),
                ));
            }
            graph.nodes.insert(from as i32, new_node);
        }

        graph
    }

    fn manhattan_distance(a: &Vec<i32>, b: &Vec<i32>) -> i32 {
        (a[0] - b[0]).abs() + (a[1] - b[1]).abs()
    }
}

the code couldn't solve [[0,0],[1,1],[1,0],[-1,1]] the answer is 4 but the result is 5, i thought it's because BinaryHeap with Reverse

2

it's 2 o'clock in my country. I love programming in rust, it's nice to see you" are replying

3

From a quick glance this seems suspicious:

You likely want the heap to be sorted according to weight, but since the first element of the tuple of to it will actually be sorted by the destination node. Reverse doesn't change this, as it only inverts the order.

Aside from that, your Edge type seems unused. Even if it was used, it's generally an error to implement Ord/PartialOrd in a way that doesn't agree with PartialEq. In your case an edge from 0to 1 with weight 2 and an edge from 3 to 4 also with weight 2 would compare different according to PartialEq and equal according to Ord, which is inconsistent.

Finally I would suggest you to write this without using Rc and RefCell. It's not wrong, but you'll likely be better off in general not using them unless strictly necessary (and in this case I don't see any reason to use them, they seem to do nothing except complicate some code)

1 Like