use std::collections::BTreeMap;

struct MyCalendarTwo {
    events: BTreeMap<i32, i32>
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCalendarTwo {

    fn new() -> Self {
        MyCalendarTwo {
            events: BTreeMap::new()
        }
    }

    fn book(&mut self, start: i32, end: i32) -> bool {
        self.events.entry(start).or_insert(0);
        self.events.entry(end).or_insert(0);
        *self.events.get_mut(&start).unwrap() += 1;
        *self.events.get_mut(&end).unwrap() -= 1;
        let mut sum = 0;
        for (_k, v) in &self.events {
            sum += *v;
            if sum == 3 {
                *self.events.get_mut(&start).unwrap() -= 1;
                *self.events.get_mut(&end).unwrap() += 1;
                return false;
            }
        }

        return true;
    }
}

use std::collections::BTreeMap;

struct MyCalendarThree {
    events: BTreeMap<i32, i32>
}


/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl MyCalendarThree {

    fn new() -> Self {
        MyCalendarThree {
            events: BTreeMap::new()
        }
    }

    fn book(&mut self, start: i32, end: i32) -> i32 {
        self.events.entry(start).or_insert(0);
        self.events.entry(end).or_insert(0);
        *self.events.get_mut(&start).unwrap() += 1;
        *self.events.get_mut(&end).unwrap() -= 1;
        let (mut count, mut ans) = (0, 0);
        for (_k, v) in &self.events {
            count += *v;
            ans = std::cmp::max(count, ans);
        }
        return ans;
    }
}

/**
 * Your MyCalendarThree object will be instantiated and called as such:
 * let obj = MyCalendarThree::new();
 * let ret_1: i32 = obj.book(start, end);
 */

use std::collections::VecDeque;
use std::collections::HashSet;

impl Solution {
    pub fn network_delay_time(times: Vec<Vec<i32>>, n: i32, k: i32) -> i32 {
        let mut ans = 0;
        let mut edges = vec![vec![-1; 101]; 101];
        let mut dist = vec![std::i32::MAX; n as usize + 1];
        dist[k as usize] = 0;
        let mut q = VecDeque::new();
        q.push_back(k);

        for e in &times {
            edges[e[0] as usize][e[1] as usize] = e[2];
        }

        while !q.is_empty() {
            let mut visited = HashSet::new();
            let size = q.len();
            for i in 0..size {
                let u = q.front().unwrap().clone() as usize; q.pop_front();
                for v in 1..101 {
                    if edges[u][v] != -1 && dist[u] + edges[u][v] < dist[v] {
                        if !visited.contains(&v) {
                            visited.insert(v);
                            q.push_back(v as i32);
                        }
                        dist[v] = dist[u] + edges[u][v];
                    }
                }
            }
        }

        for i in 1..n + 1 {
            ans = std::cmp::max(ans, dist[i as usize]);
        }

        match ans {
            std::i32::MAX => -1,
            _ => ans
        }
    }
}