Sadonkorjuu

warning: unused variable: `min_dists`
  --> input/code.rs:83:13
   |
83 |     let mut min_dists = vec![0usize; n_cities];
   |             ^^^^^^^^^ help: if this is intentional, prefix it with an underscore: `_min_dists`
   |
   = note: `#[warn(unused_variables)]` on by default

warning: variable does not need to be mutable
  --> input/code.rs:83:9
   |
83 |     let mut min_dists = vec![0usize; n_cities];
   |         ----^^^^^^^^^
   |         |
   |         help: remove this `mut`
   |
   = note: `#[warn(unused_mut)]` on by default

warning: 2 warnings emitted

use std::collections::{HashMap, BinaryHeap};

#[derive(Eq)]
struct Path {
    cur_node: usize,
    last_node: Option<usize>,
    length: usize,
}

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

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

impl PartialEq for Path {
    fn eq(&self, other: &Self) -> bool {
        self.length.eq(&other.length)
    }
}

fn sort(i: usize, j: usize) -> (usize, usize) {
    if i < j {
        (i, j)
    } else {
        (j, i)
    }
}

fn main() {
    let stdin = std::io::stdin();

    let mut input = String::new();

    stdin.read_line(&mut input).unwrap();
    let n_cities = input.trim().parse::<usize>().unwrap();
    input.clear();

    stdin.read_line(&mut input).unwrap();

    // true on satama, false on pelto
    let types = input.split_whitespace().map(|c| c.chars().next().unwrap() == '0').collect::<Vec<_>>();
    input.clear();

    let mut lenmap = HashMap::new();
    let mut bridgemap: HashMap<usize, Vec<usize>> = HashMap::new();

    loop {
        let res = stdin.read_line(&mut input).unwrap();

        if res == 0 {
            break;
        };

        let mut nums = input.split_whitespace().map(|c| c.parse::<usize>().unwrap());
        let (i, j) = (nums.next().unwrap() - 1, nums.next().unwrap() - 1);

        let (i, j) = sort(i, j);

        lenmap.insert((i, j), nums.next().unwrap());

        if let Some(vec) = bridgemap.get_mut(&i) {
            vec.push(j)
        } else {
            bridgemap.insert(i, vec![j]);
        }

        if let Some(vec) = bridgemap.get_mut(&j) {
            vec.push(i)
        } else {
            bridgemap.insert(j, vec![i]);
        }

        input.clear();
    }

    let mut min_dists = vec![0usize; n_cities];

    let sum = types.iter().enumerate().filter_map(|(i, &t)| {
        if t {
            return None;
        }

        let mut min_dist: Option<usize> = None;

        let mut paths = BinaryHeap::new();

        paths.push(Path {
            cur_node: i,
            last_node: None,
            length: 0
        });

        while let Some(path) = paths.pop() {
            if let Some(dist) = min_dist {
                if path.length > dist {
                    continue;
                }
            }

            let other_nodes = bridgemap.get(&path.cur_node).unwrap().clone();

            for other_node in other_nodes {
                if let Some(last_node) = path.last_node {
                    if other_node == last_node {
                        continue;
                    }
                };

                let new_length = path.length + *lenmap.get(&sort(other_node, path.cur_node)).unwrap();

                if let Some(dist) = min_dist {
                    if new_length >= dist {
                        continue
                    };
                };

                if !types[other_node] {
                    paths.push(Path {
                        cur_node: other_node,
                        last_node: Some(path.cur_node),
                        length: new_length
                    });
                } else {
                    if let Some(dist) = min_dist {
                        if new_length < dist {
                            min_dist = Some(new_length);
                        }
                    } else {
                        min_dist = Some(new_length);
                    }
                }
            }
        }

        min_dist
    }).sum::<usize>();

    println!("{}", sum);
}

Test 1

Group: 1, 2

Verdict: ACCEPTED

Test 2

Group: 1, 2

Verdict: ACCEPTED

Test 3

Group: 1, 2

Verdict: ACCEPTED

Test 4

Group: 1, 2

Verdict: ACCEPTED

Test 5

Group: 1, 2

Verdict: ACCEPTED

Test 6

Group: 1, 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 8

Group: 1, 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 10

Group: 1, 2

Verdict: ACCEPTED

Test 11

Group: 2

Verdict: ACCEPTED

Test 12

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2

Verdict: ACCEPTED

Test 14

Group: 2

Verdict: ACCEPTED

Test 15

Group: 1, 2

Verdict: ACCEPTED

Test 16

Group: 1, 2

Verdict: ACCEPTED

Test 17

Group: 1, 2

Verdict: ACCEPTED

Test 18

Group: 1, 2

Verdict: ACCEPTED

Test 19

Group: 1, 2

Verdict: ACCEPTED

Test 20

Group: 1, 2

Verdict: ACCEPTED

Test 21

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 2

Verdict: ACCEPTED

Test 23

Group: 2

Verdict: ACCEPTED

Test 24

Group: 1, 2

Verdict: ACCEPTED

Test 25

Group: 2

Verdict: ACCEPTED

Test 26

Group: 1, 2

Verdict: ACCEPTED

Test 27

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 28

Group: 1, 2

Verdict: ACCEPTED

Test 29

Group: 2

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 1, 2

Verdict: ACCEPTED

Test 31

Group: 2

Verdict: TIME LIMIT EXCEEDED